Domain 2MediumMEDIUM

Team Scores in Football Tournament

Calculate team points from match results using a hash map for aggregation, then sort by score descending and name ascending.

Domain: medium•Updated: 2026-09-10
#Aggregation#Dictionary#O(N + T log T)#O(T)

Problem Breakdown

The problem requires aggregating football scores based on Matches data. We must calculate total points where wins yield 3 points, draws yield 1 point (shared), and losses yield 0. The output is a list of (team_name, score) tuples sorted by score descending, then name ascending.

Inputs:

  • A list of match dictionaries containing host_team, guest_team, score_host, score_guest.

Outputs:

  • Sorted list of team scores for all teams that participated in matches (based on the provided function signature). Note: If a separate Teams table exists requiring inactive teams to be included with 0 points, this solution assumes only active participants are returned unless explicitly passed.

Intuition

The core challenge is efficiently accumulating state across multiple records without re-scanning data repeatedly. A Hash Map (Dictionary) allows O(1)O(1) updates per match record. After processing all matches in a single pass (O(N)O(N)), we sort the resulting collection. Sorting takes O(Tlog⁡T)O(T \log T) where TT is unique teams. This approach avoids nested loops and ensures optimal performance for large datasets.

Approach

  1. Initialize: Use defaultdict(int) to automatically handle team initialization with a score of 0, avoiding manual checks or KeyError exceptions.
  2. Process Matches: Iterate through each match record:
    • Extract host/guest teams and scores.
    • Compare scores to determine outcome (Win/Loss/Draw).
    • Update the corresponding team’s total points in the map accordingly (+3 for win, +1 for draw).
  3. Sort: Convert dictionary items to a list of tuples. Sort using key=lambda x: (-x[1], x[0]) to achieve descending score and ascending name ordering simultaneously.
  4. Return: Return the sorted list formatted as (name, score).

Complexity Analysis

  • Time Complexity: O(N+Tlog⁡T)O(N + T \log T) where NN is number of matches (linear scan for aggregation) and TT is unique teams (≤N\le N). The sorting step dominates if team count approaches match count.
  • Space Complexity: O(T)O(T) to store the points map. We do not need additional storage proportional to matches beyond this structure, as we aggregate immediately into the dictionary.

Solution

from collections import defaultdict
from typing import List, Dict, Tuple

def get_team_scores(matches: List[Dict]) -> List[Tuple[str, int]]:
    """
    Calculates total points for each team based on match results.
    
    Args:
        matches: A list of dictionaries with keys 'host_team', 'guest_team', 
                 'score_host', and 'score_guest'.
                 
    Returns:
        List of tuples (team_name, score) sorted by score DESC then name ASC.
    """
    # Initialize points for all teams found in the matches to 0 using defaultdict
    team_points = defaultdict(int)

    for match in matches:
        host_team = match['host_team']
        guest_team = match['guest_team']
        
        score_host = match['score_host']
        score_guest = match['score_guest']

        if score_host > score_guest:
            team_points[host_team] += 3
        elif score_guest > score_host:
            team_points[guest_team] += 3
        else: # Draw
            team_points[host_team] += 1
            team_points[guest_team] += 1

    # Convert to list of tuples and sort by points descending, then name ascending
    results = sorted(team_points.items(), key=lambda x: (-x[1], x[0]))
    
    return [(name, score) for name, score in results]

Edge Cases Handled

  • No Matches: If matches is empty, the loop skips and returns an empty list. This assumes only active participants are required; if inactive teams must be included with 0 points, a separate initialization step using a Teams table would be necessary outside this function scope.
  • Draws: Explicitly handled by adding 1 point to both host and guest when scores are equal (else branch).
  • Tie-Breaking: The sorting key uses -x[1] (descending points) followed by x[0] (ascending name), ensuring deterministic ordering for identical scores.
  • Redundant Checks Removed: The original code contained a redundant check (if not team_points[...]) which was removed in the corrected version to improve readability and efficiency, as defaultdict handles initialization automatically.