LeetCode 3384 - Team Dominance by Pass Success

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

This problem asks us to compute a dominance score for each football team across two halves of a match, based on passing outcomes. The input is represented using two database tables, Teams and Passes.

The Teams table maps every player to exactly one team. Since player_id is unique, each player belongs to only one team for the duration of the match.

The Passes table records every pass attempt during the match. Each row tells us:

which player made the pass (pass_from)
when the pass occurred (time_stamp)
which player received the pass (pass_to)

The scoring rules depend on whether the pass stays within the same team or is intercepted by the opposing team:

If both players belong to the same team, the passing team gains +1
If the receiving player belongs to the opposing team, the passing team loses 1

The match is split into two separate periods:

First half: 00:00 through 45:00
Second half: 45:01 through 90:00

For every team and for each half independently, we must compute the total dominance score.

The output should contain:

team_name
half_number
dominance

The result must be sorted by team_name ascending and then by half_number ascending.

The important observation is that the dominance score is determined entirely by the team of the passer and the team of the receiver. Every pass contributes exactly one point, either +1 or -1.

The timestamps are stored as strings, which can easily lead to implementation mistakes. Fortunately, the format is fixed as MM:SS, so lexicographical comparison works correctly. For example:

"44:59" < "45:00"
"46:00" > "45:00"

This allows us to classify halves directly using string comparison.

Several edge cases are important:

A team may have only interceptions in a half, resulting in a negative score
A team may have no passes in one half
Passes exactly at "45:00" belong to the first half
Passes at "45:01" belong to the second half
A pass may go to the opposing team, which must decrease the score instead of increasing it

The problem guarantees valid player IDs, so every pass_from and pass_to exists in the Teams table.

Approaches

Brute Force Approach

A straightforward solution would process every pass and repeatedly search the Teams table to determine the teams for both the passer and the receiver.

For each pass:

Scan the Teams table to find the team of pass_from
Scan the Teams table again to find the team of pass_to
Determine the half using the timestamp
Add +1 or -1 to the correct team's score

This approach is correct because every pass is individually evaluated according to the problem rules. However, it is inefficient because each lookup requires scanning the entire Teams table.

If there are P passes and T players, the complexity becomes O(P * T).

Optimal Approach

The key optimization is to preprocess the Teams table into a hash map:

player_id -> team_name

With this structure, team lookup becomes O(1) instead of O(T).

Then we iterate through the Passes table exactly once:

Determine the half from the timestamp
Use the hash map to identify both teams
Compute whether the pass is successful or intercepted
Update the dominance score in an aggregated result structure

This reduces the total complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(P * T)	O(1)	Repeatedly scans Teams table for every pass
Optimal	O(P + T)	O(T)	Uses hash map for constant-time team lookup

Algorithm Walkthrough

Build a mapping from player IDs to team names.

We first create a dictionary using the Teams table:

player_to_team[player_id] = team_name

This preprocessing step allows us to instantly determine which team any player belongs to. 2. Initialize a structure to store dominance scores.

We need to aggregate scores by both team and half number. A convenient structure is:

scores[(team_name, half_number)] = dominance

Iterate through every pass.

For each row in Passes, retrieve:

pass_from
pass_to
time_stamp

Determine the match half.

Since timestamps are stored in fixed-width MM:SS format, we can compare strings directly.

If time_stamp <= "45:00", the pass belongs to half 1
Otherwise, it belongs to half 2

Identify the teams.

Using the hash map:

from_team = player_to_team[pass_from]
to_team = player_to_team[pass_to]

Compute the score contribution.

If from_team == to_team, this is a successful pass, add +1
Otherwise, this is an interception, add -1

Update the aggregated dominance score.

Add the contribution to:

scores[(from_team, half_number)]

The score is always credited to the passing team. 8. Return the final result.

Sort the output by:

team_name
half_number

in ascending order.

Why it works

The algorithm works because every pass contributes independently to exactly one team's dominance score in exactly one half. The hash map guarantees correct team identification in constant time, and the aggregation structure ensures all contributions for the same team and half are accumulated together. Since every pass is processed once and scored according to the problem definition, the final totals are correct.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def teamDominance(self, teams: List[List], passes: List[List]) -> List[List]:
        # Map each player to their team
        player_to_team = {}

        for player_id, team_name in teams:
            player_to_team[player_id] = team_name

        # Store dominance scores
        dominance_scores = defaultdict(int)

        # Process every pass
        for pass_from, time_stamp, pass_to in passes:
            from_team = player_to_team[pass_from]
            to_team = player_to_team[pass_to]

            # Determine half number
            half_number = 1 if time_stamp <= "45:00" else 2

            # Successful pass or interception
            if from_team == to_team:
                dominance_scores[(from_team, half_number)] += 1
            else:
                dominance_scores[(from_team, half_number)] -= 1

        # Build result
        result = []

        for (team_name, half_number), dominance in dominance_scores.items():
            result.append([team_name, half_number, dominance])

        # Sort by team_name, then half_number
        result.sort(key=lambda x: (x[0], x[1]))

        return result

The implementation begins by constructing the player_to_team dictionary. This is the preprocessing step that converts repeated team lookups from linear time into constant time operations.

Next, a defaultdict(int) is used to accumulate dominance scores. This avoids manual initialization because missing keys automatically start at zero.

The main loop processes each pass exactly once. For every pass, the code retrieves both the passer's team and the receiver's team. The timestamp comparison determines whether the pass belongs to the first or second half.

The scoring logic directly mirrors the problem statement:

same team means successful pass, add 1
different teams means interception, subtract 1

Finally, the aggregated results are converted into the required output format and sorted according to the specification.

Go Solution

package main

import (
	"sort"
)

type Solution struct{}

func (s Solution) teamDominance(teams [][]interface{}, passes [][]interface{}) [][]interface{} {
	// Map player -> team
	playerToTeam := make(map[int]string)

	for _, team := range teams {
		playerID := team[0].(int)
		teamName := team[1].(string)

		playerToTeam[playerID] = teamName
	}

	// Store dominance scores
	dominanceScores := make(map[[2]interface{}]int)

	// Process passes
	for _, pass := range passes {
		passFrom := pass[0].(int)
		timeStamp := pass[1].(string)
		passTo := pass[2].(int)

		fromTeam := playerToTeam[passFrom]
		toTeam := playerToTeam[passTo]

		halfNumber := 1
		if timeStamp > "45:00" {
			halfNumber = 2
		}

		key := [2]interface{}{fromTeam, halfNumber}

		if fromTeam == toTeam {
			dominanceScores[key]++
		} else {
			dominanceScores[key]--
		}
	}

	// Build result
	result := make([][]interface{}, 0)

	for key, dominance := range dominanceScores {
		teamName := key[0].(string)
		halfNumber := key[1].(int)

		result = append(result, []interface{}{
			teamName,
			halfNumber,
			dominance,
		})
	}

	// Sort result
	sort.Slice(result, func(i, j int) bool {
		teamI := result[i][0].(string)
		teamJ := result[j][0].(string)

		if teamI == teamJ {
			return result[i][1].(int) < result[j][1].(int)
		}

		return teamI < teamJ
	})

	return result
}

The Go implementation follows the same logic as the Python version. The primary difference is that Go requires explicit type assertions when extracting values from interface{} arrays.

A Go map is used for both the player-to-team lookup and the dominance aggregation. Sorting is performed with sort.Slice, using a custom comparator that orders first by team name and then by half number.

Go does not have a built-in equivalent of Python's defaultdict, so missing map entries naturally default to zero values for integers.

Worked Examples

Example 1

Input:

Teams:
1 -> Arsenal
2 -> Arsenal
3 -> Arsenal
4 -> Chelsea
5 -> Chelsea
6 -> Chelsea

Process each pass step by step.

Pass	Half	From Team	To Team	Score Change	Running Total
1 -> 2 at 00:15	1	Arsenal	Arsenal	+1	Arsenal,1 = 1
2 -> 3 at 00:45	1	Arsenal	Arsenal	+1	Arsenal,1 = 2
3 -> 1 at 01:15	1	Arsenal	Arsenal	+1	Arsenal,1 = 3
4 -> 1 at 00:30	1	Chelsea	Arsenal	-1	Chelsea,1 = -1
2 -> 3 at 46:00	2	Arsenal	Arsenal	+1	Arsenal,2 = 1
3 -> 4 at 46:15	2	Arsenal	Chelsea	-1	Arsenal,2 = 0
1 -> 2 at 46:45	2	Arsenal	Arsenal	+1	Arsenal,2 = 1
5 -> 6 at 46:30	2	Chelsea	Chelsea	+1	Chelsea,2 = 1

Final result:

team_name	half_number	dominance
Arsenal	1	3
Arsenal	2	1
Chelsea	1	-1
Chelsea	2	1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(T + P)	Building the player map takes O(T), processing passes takes O(P)
Space	O(T + R)	Stores player lookup map and dominance aggregation results

Here, T is the number of players, P is the number of passes, and R is the number of distinct (team, half) result entries.

The algorithm is linear because every player and every pass is processed exactly once. Hash map lookups and updates are constant time on average.

Test Cases

sol = Solution()

# Example case from the problem statement
assert sorted(sol.teamDominance(
    [
        [1, "Arsenal"],
        [2, "Arsenal"],
        [3, "Arsenal"],
        [4, "Chelsea"],
        [5, "Chelsea"],
        [6, "Chelsea"]
    ],
    [
        [1, "00:15", 2],
        [2, "00:45", 3],
        [3, "01:15", 1],
        [4, "00:30", 1],
        [2, "46:00", 3],
        [3, "46:15", 4],
        [1, "46:45", 2],
        [5, "46:30", 6]
    ]
)) == sorted([
    ["Arsenal", 1, 3],
    ["Arsenal", 2, 1],
    ["Chelsea", 1, -1],
    ["Chelsea", 2, 1]
])  # Basic mixed scenario

# Single successful pass in first half
assert sol.teamDominance(
    [
        [1, "A"],
        [2, "A"]
    ],
    [
        [1, "10:00", 2]
    ]
) == [
    ["A", 1, 1]
]  # Successful pass

# Single interception
assert sol.teamDominance(
    [
        [1, "A"],
        [2, "B"]
    ],
    [
        [1, "20:00", 2]
    ]
) == [
    ["A", 1, -1]
]  # Intercepted pass

# Boundary timestamp at 45:00
assert sol.teamDominance(
    [
        [1, "A"],
        [2, "A"]
    ],
    [
        [1, "45:00", 2]
    ]
) == [
    ["A", 1, 1]
]  # Exact first-half boundary

# Boundary timestamp at 45:01
assert sol.teamDominance(
    [
        [1, "A"],
        [2, "A"]
    ],
    [
        [1, "45:01", 2]
    ]
) == [
    ["A", 2, 1]
]  # Exact second-half boundary

# Multiple teams and mixed outcomes
assert sorted(sol.teamDominance(
    [
        [1, "A"],
        [2, "A"],
        [3, "B"],
        [4, "B"]
    ],
    [
        [1, "05:00", 2],
        [1, "10:00", 3],
        [3, "50:00", 4],
        [4, "55:00", 1]
    ]
)) == sorted([
    ["A", 1, 0],
    ["B", 2, 0]
])  # Positive and negative scores cancel out

Test	Why
Problem statement example	Validates standard mixed behavior
Single successful pass	Confirms +1 scoring
Single interception	Confirms -1 scoring
Timestamp 45:00	Verifies first-half boundary
Timestamp 45:01	Verifies second-half boundary
Mixed multi-team scenario	Ensures aggregation and cancellation work correctly

Edge Cases

One important edge case is handling timestamps at the boundary between halves. The specification explicitly states that 45:00 belongs to the first half, while 45:01 belongs to the second half. A careless implementation might incorrectly classify 45:00 into the second half. This solution correctly handles the boundary by using the condition:

time_stamp <= "45:00"

Another important edge case is interceptions. It is easy to accidentally award points to the receiving team instead of subtracting points from the passing team. The implementation avoids this mistake by always updating the score associated with from_team.

A third edge case occurs when a team has no passes in one half. In that situation, no entry should be created for that team and half combination. Since the implementation only creates entries when processing actual passes, it naturally avoids generating unnecessary rows with zero dominance values.