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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Players With Zero or One Losses

Number: 1354

Difficulty: Medium

Paid? No

Companies: Palantir Technologies, Amazon, Indeed

Problem Description

Given a list of match results where each match is represented as [winner, loser], return an answer containing two lists: the first list contains players who have never lost a match, and the second list contains players who have lost exactly one match. The answer lists should be sorted in increasing order. Only players that have played at least one match should be considered.

Key Insights

  • Use a hash map to count losses for each player.
  • Ensure that players who only won matches and never lost are recorded (loss count = 0).
  • After processing all matches, iterate through the loss counts to filter players with 0 or 1 loss.
  • Sort the resulting lists before returning.

Space and Time Complexity

Time Complexity: O(n + u log u), where n is the number of matches and u is the number of unique players (sorting the players incurs the log factor). Space Complexity: O(u) for storing loss counts for each unique player.

Solution

The solution involves iterating over the matches and using a hash table (dictionary) to track the number of losses per player. For every match, increment the loss count for the loser and ensure the winner is accounted for in the hash table (with 0 losses if not already present). After processing all matches, iterate through the hash table to collect players with 0 losses and those with 1 loss. Finally, sort both lists to satisfy the order requirement. This approach efficiently counts losses and then filters and sorts the players accordingly.

Code Solutions

# Python solution for finding players with zero or one losses

def findWinners(matches):
    # Dictionary to store the number of losses for each player
    loss_count = {}
    
    # Process each match
    for winner, loser in matches:
        # Ensure winner is recorded with 0 losses if not present
        if winner not in loss_count:
            loss_count[winner] = 0
        # Increment loss count for the loser
        loss_count[loser] = loss_count.get(loser, 0) + 1

    # Initialize lists for players with zero and one loss
    zero_losses = []
    one_loss = []
    
    # Filter players based on loss count
    for player, losses in loss_count.items():
        if losses == 0:
            zero_losses.append(player)
        elif losses == 1:
            one_loss.append(player)
    
    # Sort the lists before returning
    return [sorted(zero_losses), sorted(one_loss)]

# Example usage:
if __name__ == "__main__":
    matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
    print(findWinners(matches))  # Expected output: [[1,2,10],[4,5,7,8]]
← Back to All Questions