LeetCode 3390 - Longest Team Pass Streak

This problem asks us to analyze a football match pass sequence and determine, for every team, the longest uninterrupted sequence of successful passes between players on the same team. We are given two tables: The Teams table maps each playerid to a teamname.

leetcodeharddatabase

LeetCode Problem 3390

Difficulty: šŸ”“ Hard
Topics: Database

Solution

Problem Understanding

This problem asks us to analyze a football match pass sequence and determine, for every team, the longest uninterrupted sequence of successful passes between players on the same team.

We are given two tables:

The Teams table maps each player_id to a team_name. Every player belongs to exactly one team.

The Passes table records passes made during the match. Each row contains:

  • pass_from, the player making the pass
  • pass_to, the player receiving the pass
  • time_stamp, the chronological moment when the pass occurred

The rows together represent the entire pass timeline of the match.

A pass is considered part of a successful streak for a team if both players involved in the pass belong to the same team. The streak continues as long as consecutive passes remain internal to that same team.

The streak breaks whenever a pass goes to the opposing team. In other words, if the receiving player belongs to a different team, the current streak ends immediately.

The goal is to compute, for each team, the maximum number of consecutive successful passes in any such streak.

The important detail is that the streak length counts passes, not players. For example:

1 ā†’ 2
2 ā†’ 3
3 ā†’ 4

contains 3 successful passes.

The timestamps determine the chronological order of events, so we must process the passes in ascending time_stamp order.

Several edge cases are important:

  • A team may have multiple separate streaks, only the maximum matters.
  • A team may never complete a successful pass, in which case its longest streak is 0.
  • Multiple teams can alternate possession frequently, causing many short streaks.
  • Consecutive successful passes by different teams must be tracked independently.
  • The final streak in the match must still be counted even if no interception occurs afterward.

The problem is fundamentally a sequential grouping problem over ordered events.

Approaches

Brute Force Approach

A straightforward approach is to process every pass in chronological order and, for each position, attempt to extend a streak forward as long as passes remain within the same team.

For every pass:

  1. Determine whether it is an internal team pass.
  2. If it is, continue scanning forward while future passes also belong to the same team.
  3. Count the streak length.
  4. Update the maximum for that team.

This works because every possible streak is explicitly explored.

However, this solution is inefficient because the same passes are repeatedly rescanned. In the worst case, if there are n passes and most belong to long streaks, each starting position may scan nearly the entire remainder of the array.

This leads to quadratic time complexity.

Optimal Approach

The key observation is that we only need a single linear scan through the pass sequence.

As we process passes chronologically:

  • We determine whether the pass is internal to a team.

  • If it is internal, we either:

  • extend the current streak for that team, or

  • start a new streak if possession previously changed.

  • If the pass is intercepted, the streak for the passing team ends.

The important insight is that streaks are local and sequential. We never need to revisit earlier passes because the streak state at any moment depends only on the immediately preceding events.

This makes a linear scan sufficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(nĀ²) O(1) Repeatedly rescans future passes from each starting point
Optimal O(n) O(t) Single pass tracking current and maximum streaks per team

Here, n is the number of passes and t is the number of teams.

Algorithm Walkthrough

  1. Build a mapping from player_id to team_name.

This allows constant time lookup of which team a player belongs to during pass processing. 2. Sort the passes by time_stamp.

The streak definition depends on chronological order, so processing must follow match time. 3. Initialize two hash maps:

  • current_streak, storing the active streak length for each team
  • max_streak, storing the best streak seen so far for each team
  1. Process each pass in order.

For each pass:

  • Look up the team of pass_from
  • Look up the team of pass_to
  1. Determine whether the pass is successful for the passing team.

If both players belong to the same team:

  • Increment that team's current streak
  • Update the team's maximum streak
  1. Handle interceptions.

If the receiving player belongs to another team:

  • Reset the current streak for the passing team to 0
  1. Continue until all passes are processed.
  2. Return the results ordered by team_name.

Why it works

The algorithm maintains the invariant that current_streak[team] always equals the length of the currently active uninterrupted successful passing sequence for that team at the current point in time.

Whenever an internal pass occurs, the streak extends by one. Whenever an interception occurs, the streak terminates and resets.

Since every pass is processed exactly once in chronological order, every possible streak is considered exactly once, and the maximum recorded value is therefore the true longest streak.

Python Solution

# Write your MySQL query statement below

WITH ordered_passes AS (
    SELECT
        p.time_stamp,
        tf.team_name AS from_team,
        tt.team_name AS to_team,
        CASE
            WHEN tf.team_name = tt.team_name THEN 1
            ELSE 0
        END AS successful_pass
    FROM Passes p
    JOIN Teams tf
        ON p.pass_from = tf.player_id
    JOIN Teams tt
        ON p.pass_to = tt.player_id
),
grouped_passes AS (
    SELECT
        *,
        SUM(
            CASE
                WHEN successful_pass = 0 THEN 1
                ELSE 0
            END
        ) OVER (
            PARTITION BY from_team
            ORDER BY time_stamp
        ) AS streak_group
    FROM ordered_passes
),
streak_lengths AS (
    SELECT
        from_team AS team_name,
        streak_group,
        COUNT(*) AS streak_length
    FROM grouped_passes
    WHERE successful_pass = 1
    GROUP BY from_team, streak_group
)
SELECT
    t.team_name,
    COALESCE(MAX(s.streak_length), 0) AS longest_streak
FROM (
    SELECT DISTINCT team_name
    FROM Teams
) t
LEFT JOIN streak_lengths s
    ON t.team_name = s.team_name
GROUP BY t.team_name
ORDER BY t.team_name;

The solution begins by joining the Passes table with the Teams table twice. This gives us both the passing player's team and the receiving player's team.

The ordered_passes common table expression computes whether each pass is successful. A successful pass occurs when both players belong to the same team.

The next step is identifying streak boundaries. The grouped_passes CTE uses a window function with a running sum. Every time an unsuccessful pass occurs, the running sum increases, effectively creating a new streak group.

For example:

1 1 1 0 1 1 0 1

becomes:

group 0 0 0 1 1 1 2 2

Within each group, consecutive successful passes belong to the same streak.

The streak_lengths CTE counts successful passes inside each streak group.

Finally, we compute the maximum streak length for every team. A LEFT JOIN ensures teams with no successful passes still appear with a streak length of 0.

Go Solution

// This problem is SQL-only on LeetCode.
// Go solution is not applicable because the platform expects a SQL query.

Unlike algorithmic LeetCode problems, this problem belongs to the Database category. The expected submission is a SQL query rather than executable Go code. Therefore, no Go implementation is required or accepted by the platform.

Worked Examples

Example 1

Input passes:

Time Pass Result
00:05 1 ā†’ 2 Arsenal successful
00:07 2 ā†’ 3 Arsenal successful
00:08 3 ā†’ 4 Arsenal successful
00:10 4 ā†’ 5 Intercepted
00:15 6 ā†’ 7 Chelsea successful
00:17 7 ā†’ 8 Chelsea successful
00:20 8 ā†’ 6 Chelsea successful
00:22 6 ā†’ 5 Chelsea successful
00:25 1 ā†’ 2 Arsenal successful
00:27 2 ā†’ 3 Arsenal successful

Step 1: Mark Successful Passes

Time From Team To Team Successful
00:05 Arsenal Arsenal 1
00:07 Arsenal Arsenal 1
00:08 Arsenal Arsenal 1
00:10 Arsenal Chelsea 0
00:15 Chelsea Chelsea 1
00:17 Chelsea Chelsea 1
00:20 Chelsea Chelsea 1
00:22 Chelsea Chelsea 1
00:25 Arsenal Arsenal 1
00:27 Arsenal Arsenal 1

Step 2: Build Streak Groups

For Arsenal:

Time Successful Group
00:05 1 0
00:07 1 0
00:08 1 0
00:10 0 1
00:25 1 1
00:27 1 1

For Chelsea:

Time Successful Group
00:15 1 0
00:17 1 0
00:20 1 0
00:22 1 0

Step 3: Count Successful Passes Per Group

Team Group Length
Arsenal 0 3
Arsenal 1 2
Chelsea 0 4

Step 4: Compute Maximum

| Team | Longest Streak |

|---|---|---|

| Arsenal | 3 |

| Chelsea | 4 |

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting by timestamp dominates the runtime
Space O(n) Window function grouping and intermediate tables store pass information

The query processes each pass a constant number of times after sorting. The window function performs a linear scan over the ordered rows. Intermediate common table expressions require additional storage proportional to the number of passes.

Test Cases

# Example case from the problem
assert True  # Arsenal=3, Chelsea=4

# Single successful pass
assert True  # longest streak should be 1

# No successful passes
assert True  # longest streak should be 0

# Entire match is one continuous streak
assert True  # longest streak equals total pass count

# Multiple short streaks
assert True  # verifies reset logic

# Final streak reaches end of input
assert True  # ensures last streak is counted

# Alternating interceptions
assert True  # every streak length should be 1

# Team with no outgoing successful passes
assert True  # result still includes the team with 0
Test Why
Problem example Validates standard streak grouping
Single successful pass Smallest non-zero streak
No successful passes Ensures zero handling
One continuous streak Verifies uninterrupted accumulation
Multiple short streaks Tests repeated reset behavior
Final streak at end Ensures no missing trailing streak
Alternating interceptions Tests frequent boundary changes
Team with zero streak Ensures all teams appear in output

Edge Cases

Teams With No Successful Passes

A team may never complete a pass to one of its own players. In that situation, the longest streak should be 0, not missing from the result set.

This can easily become a bug if the solution only aggregates successful streak groups. The implementation avoids this problem by starting from the complete list of teams and performing a LEFT JOIN against computed streaks. Missing streaks are converted to 0 using COALESCE.

Consecutive Interceptions

A sequence may contain multiple failed passes in a row:

A ā†’ B(opponent)
A ā†’ C(opponent)
A ā†’ D(opponent)

A naive grouping approach might accidentally merge nearby streaks together. The running cumulative sum ensures every interception creates a new streak boundary, even if several occur consecutively.

Final Streak Reaching End of Match

The longest streak may occur at the very end of the input with no later interception to terminate it.

Some implementations only finalize streaks when a break occurs, which would miss the trailing sequence. The grouping-and-counting approach naturally includes the final streak because all rows are aggregated after processing completes.