{x}
blog image

Find Players With Zero or One Losses

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.

Note:

  • You should only consider the players that have played at least one match.
  • The testcases will be generated such that no two matches will have the same outcome.

 

Example 1:

Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].

Example 2:

Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.
Thus, answer[0] = [1,2,5,6] and answer[1] = [].

 

Constraints:

  • 1 <= matches.length <= 105
  • matches[i].length == 2
  • 1 <= winneri, loseri <= 105
  • winneri != loseri
  • All matches[i] are unique.

Problem Description

The problem asks to find all players who have either zero or one loss in a series of matches. The input is a list of matches, where each match is represented as a pair [winner, loser]. The output should be a list of two lists: the first list contains players with zero losses, and the second list contains players with exactly one loss. Both lists should be sorted in ascending order.

Approach

The most efficient approach uses a hash map (dictionary in Python) to count the number of losses for each player. We iterate through the matches list. For each match, we increment the loss count for the loser. If a player is a winner, we either add them to the map with a count of 0 or leave their count unchanged (since they didn't lose). After processing all matches, we iterate through the hash map. Players with 0 losses are added to the first list, and players with 1 loss are added to the second list. Finally, both lists are sorted before returning the result.

Time and Space Complexity Analysis

  • Time Complexity: The dominant operations are iterating through the matches list (O(m) where m is the number of matches) and iterating through the hash map (O(n) where n is the number of unique players, which is at most 2m). Sorting the two output lists adds O(n log n) time complexity (assuming efficient sorting algorithms like merge sort or quicksort). Therefore, the overall time complexity is O(m + n log n), which can be simplified to O(m log m) in the worst case since n ≤ 2m.

  • Space Complexity: The hash map stores the loss count for each player, requiring O(n) space. The output lists also take O(n) space in the worst case. Therefore, the overall space complexity is O(n).

Code Implementation (with explanations)

The solutions below use a hash map (or its equivalent in each language) to count losses efficiently.

Python:

from collections import Counter
 
class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        losses = Counter()  # Use Counter for efficient counting
        players = set()     # Keep track of all players
 
        for winner, loser in matches:
            losses[loser] += 1
            players.add(winner)
            players.add(loser)
 
        zero_losses = []
        one_loss = []
 
        for player in players:
            if losses[player] == 0:
                zero_losses.append(player)
            elif losses[player] == 1:
                one_loss.append(player)
 
        zero_losses.sort()
        one_loss.sort()
        return [zero_losses, one_loss]

Java:

import java.util.*;
 
class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        Map<Integer, Integer> losses = new HashMap<>();
        Set<Integer> players = new HashSet<>();
 
        for (int[] match : matches) {
            losses.put(match[1], losses.getOrDefault(match[1], 0) + 1); // Increment loser's losses
            players.add(match[0]);
            players.add(match[1]);
        }
 
        List<List<Integer>> result = new ArrayList<>(Arrays.asList(new ArrayList<>(), new ArrayList<>()));
 
        for (int player : players) {
            int numLosses = losses.getOrDefault(player, 0);
            if (numLosses == 0) {
                result.get(0).add(player);
            } else if (numLosses == 1) {
                result.get(1).add(player);
            }
        }
 
        Collections.sort(result.get(0));
        Collections.sort(result.get(1));
        return result;
    }
}

JavaScript:

/**
 * @param {number[][]} matches
 * @return {number[][]}
 */
var findWinners = function(matches) {
    const losses = {};
    const players = new Set();
 
    for (const [winner, loser] of matches) {
        losses[loser] = (losses[loser] || 0) + 1;
        players.add(winner);
        players.add(loser);
    }
 
    const zeroLosses = [];
    const oneLoss = [];
 
    for (const player of players) {
        const numLosses = losses[player] || 0;
        if (numLosses === 0) {
            zeroLosses.push(player);
        } else if (numLosses === 1) {
            oneLoss.push(player);
        }
    }
 
    zeroLosses.sort((a, b) => a - b);
    oneLoss.sort((a, b) => a - b);
    return [zeroLosses, oneLoss];
};

(Other languages like C++, Go, TypeScript would follow similar patterns using their respective hash map and sorting implementations).

These implementations all follow the described approach and achieve the optimal time and space complexity. Remember to adapt the code to your specific language's standard library functions for hash maps and sorting.