LeetCode 2173 - Longest Winning Streak

LeetCode Problem 2173

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

This problem is asking us to determine the longest sequence of consecutive wins, also called a winning streak, for each player in a match history. The input is a Matches table with three columns: player_id, match_day, and result. Each row represents one match played by a specific player on a given day, with the match result being either Win, Draw, or Lose. The combination (player_id, match_day) is guaranteed to be unique, which ensures that each match is distinct.

The expected output is a table that lists every player_id along with their longest winning streak, which is the maximum number of consecutive matches that ended in a Win without any Draw or Lose interrupting the sequence. If a player has never won a match, their longest streak is 0.

Key constraints and observations include:

1. Matches are not guaranteed to be consecutive in dates for a player.
2. A streak is only broken by Draw or Lose.
3. The dataset can have multiple players, each with varying numbers of matches.
4. Edge cases include players who never win, players with only one match, and players whose wins are scattered with draws or losses.

Understanding these constraints ensures we handle both sparse and dense match histories, and correctly compute consecutive sequences without miscounting.

Approaches

Brute-Force Approach

A straightforward approach would involve iterating through each player’s matches sorted by match_day and maintaining a counter for consecutive wins. Whenever a Draw or Lose is encountered, we reset the counter and update the maximum streak. While this approach is simple and guarantees correct results, it requires sorting matches for each player and iterating through them, which is potentially inefficient for large datasets. The database implementation might require multiple scans or complex subqueries to achieve this.

Optimal Approach

The key insight for an optimal solution is to use SQL window functions, specifically ROW_NUMBER(), to identify contiguous sequences of wins. By assigning a row number to each match in chronological order and then computing a “group identifier” as the difference between the row number and a cumulative count of wins, we can segment winning streaks efficiently. This allows grouping consecutive wins together and counting them in a single query. This approach avoids repeated scans and leverages the database's set-based operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Sort matches per player and iterate to compute streaks
Optimal	O(n)	O(n)	Use window functions to group consecutive wins and compute max streak

Algorithm Walkthrough

1. Partition the matches by player_id and order them by match_day using the ROW_NUMBER() window function.
2. Create a cumulative count of wins per player using a running sum, treating Win as 1 and others as 0.
3. Compute a group identifier for consecutive wins by subtracting the cumulative win count from the row number. This groups consecutive wins together while ignoring Draw and Lose.
4. Filter only Win matches, as only wins contribute to a streak.
5. Group by player_id and the calculated group identifier, counting matches in each winning streak.
6. Compute the maximum streak per player using MAX.
7. Ensure players who have never won a match are included with a streak of 0 using a LEFT JOIN or COALESCE.

Why it works: The difference between row number and cumulative win count remains constant for consecutive wins. When a non-win occurs, the difference changes, effectively segmenting winning streaks. Counting within these segments produces the correct length for each streak, and taking the maximum per player yields the desired result.

Python Solution

import sqlite3
from typing import List, Tuple

def longest_winning_streak(conn: sqlite3.Connection) -> List[Tuple[int, int]]:
    query = """
    WITH numbered AS (
        SELECT
            player_id,
            match_day,
            result,
            ROW_NUMBER() OVER(PARTITION BY player_id ORDER BY match_day) AS rn,
            SUM(CASE WHEN result = 'Win' THEN 1 ELSE 0 END) OVER(PARTITION BY player_id ORDER BY match_day ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS win_count
        FROM Matches
    ),
    streaks AS (
        SELECT
            player_id,
            rn - win_count AS grp
        FROM numbered
        WHERE result = 'Win'
    )
    SELECT
        m.player_id,
        COALESCE(MAX(COUNT(s.grp)) OVER(PARTITION BY m.player_id), 0) AS longest_streak
    FROM Matches m
    LEFT JOIN streaks s ON m.player_id = s.player_id
    GROUP BY m.player_id
    """
    cursor = conn.cursor()
    cursor.execute(query)
    return cursor.fetchall()

This Python solution executes a single SQL query using SQLite. It uses a common table expression (CTE) to compute row numbers and cumulative wins, then identifies streaks by grouping. Finally, it computes the maximum streak for each player while handling players with no wins using COALESCE.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
)

func LongestWinningStreak(db *sql.DB) ([]struct{PlayerID, LongestStreak int}, error) {
    query := `
    WITH numbered AS (
        SELECT
            player_id,
            match_day,
            result,
            ROW_NUMBER() OVER(PARTITION BY player_id ORDER BY match_day) AS rn,
            SUM(CASE WHEN result = 'Win' THEN 1 ELSE 0 END) OVER(PARTITION BY player_id ORDER BY match_day ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS win_count
        FROM Matches
    ),
    streaks AS (
        SELECT
            player_id,
            rn - win_count AS grp
        FROM numbered
        WHERE result = 'Win'
    )
    SELECT
        m.player_id,
        COALESCE(MAX(COUNT(s.grp)) OVER(PARTITION BY m.player_id), 0) AS longest_streak
    FROM Matches m
    LEFT JOIN streaks s ON m.player_id = s.player_id
    GROUP BY m.player_id
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results []struct{ PlayerID, LongestStreak int }
    for rows.Next() {
        var r struct{ PlayerID, LongestStreak int }
        if err := rows.Scan(&r.PlayerID, &r.LongestStreak); err != nil {
            return nil, err
        }
        results = append(results, r)
    }
    return results, nil
}

In Go, the solution executes the same SQL query and scans results into a slice of structs. Go requires explicit handling of SQL rows and errors, and there is no COALESCE equivalent in Go code, as it is handled in SQL.

Worked Examples

Example 1

For player 1:

match_day	result	rn	win_count	grp
2022-01-17	Win	1	1	0
2022-01-18	Win	2	2	0
2022-01-25	Win	3	3	0
2022-01-31	Draw	4	3	-
2022-02-08	Win	5	4	1

The groups for wins are 0 and 1, giving streaks of lengths 3 and 1. Maximum is 3.

Player 2 has no wins, so maximum streak is 0.

Player 3 has one win, so maximum streak is 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each match is processed once; window functions compute row numbers and cumulative sums efficiently
Space	O(n)	Storing row numbers, cumulative sums, and grouping requires extra space proportional to number of matches

The algorithm leverages database-level window functions, avoiding explicit nested loops, making it scalable for large tables.

Test Cases

# test cases
assert longest_winning_streak(conn) == [(1, 3), (2, 0), (3, 1)]  # Example 1
# Player with all losses
assert longest_winning_streak(conn_loss_only) == [(1, 0)]
# Player with alternating wins and draws
assert longest_winning_streak(conn_alternating) == [(1, 1)]
# Player with a single match win
assert longest_winning_streak(conn_single_win) == [(1, 1)]
# Multiple players with mixed results
assert longest_winning_streak(conn_multiple) == [(1, 3), (2, 2), (3, 1)]

Test	Why
Example 1	Validates basic streak calculation
All losses	Ensures streak 0 is handled correctly
Alternating wins/draws	Tests streak resets on non-win
Single match win	Edge case for minimal input
Multiple players	Checks correctness with multiple IDs

Edge Cases

One important edge case is a player who never