We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Players With Zero or One Losses

Difficulty: Medium

Problem Description

You are given an integer array matches where matches[i] = [winneri, loseri] indicates that the player winneri defeated player loseri in a match. Return a list answer of size 2 where: answer[0] is a list of all players that have not lost any matches. answer[1] is a list of all players that have lost exactly one match. The values in the two lists should be returned in increasing order.

Key Insights

  • Players can be tracked using a hash table to count losses.
  • A set can be used to keep track of players who have not lost any matches.
  • Sorting is necessary to return the lists in increasing order.
  • Players with no matches should not be included in the final output.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the final lists.
Space Complexity: O(n) - for storing counts of losses and the players.

Solution

To solve the problem, we will utilize two hash tables (or dictionaries) to track the number of losses for each player and a set to track players who have not lost any matches. We iterate through the list of matches, updating the loss counts for each player. After processing all matches, we will collect the players into two lists based on their loss counts: one for players with zero losses and another for players with exactly one loss. Finally, we will sort both lists before returning them.

Code Solutions

def findWinners(matches):
    loss_count = {}
    for winner, loser in matches:
        if winner not in loss_count:
            loss_count[winner] = 0
        loss_count[winner] += 0  # Winner losses remain zero
        
        if loser not in loss_count:
            loss_count[loser] = 0
        loss_count[loser] += 1  # Increment loss count for loser
        
    # Prepare two lists for players with 0 losses and 1 loss
    no_loss = []
    one_loss = []
    
    for player, losses in loss_count.items():
        if losses == 0:
            no_loss.append(player)
        elif losses == 1:
            one_loss.append(player)
    
    # Sort both lists
    return [sorted(no_loss), sorted(one_loss)]
← Back to All Questions