Find Players With Zero or One Losses

Med

#2028Time: O(M + P log P), where M is the number of matches and P is the number of unique players. It takes O(M) to populate the HashMap. Then, it takes O(P) to iterate through the map and O(P log P) to sort the result lists. The sorting step dominates the complexity.Space: O(P), where P is the number of unique players. This space is used to store the `lossesCount` map and the final result lists.2 companies

Patterns

Counting

Algorithms

Sorting

Data structures

Array Hash Table

Companies

Indeed Palantir Technologies

Prompt

You are given an integer array matches where matches[i] = [winner_i, loser_i] indicates that the player winner_i defeated player loser_i 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 <= 10⁵
matches[i].length == 2
1 <= winner_i, loser_i <= 10⁵
winner_i != loser_i
All matches[i] are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a HashMap to store the number of losses for each player. We first iterate through all the matches to populate this map. It's important to also add players who only win to the map, so we can identify them later. After counting all losses, we iterate through the map's entries to categorize players into those with zero or one loss. Finally, since the output requires sorted lists, we sort these two lists before returning the result.

Algorithm

Initialize a HashMap<Integer, Integer> called lossesCount to store the loss count for each player.
Iterate through the matches array. For each match [winner, loser]:
- Ensure the winner is in the map. If they are not present, add them with a loss count of 0. This is crucial for players who never lose.
- Increment the loss count for the loser. If they are not in the map, add them with a count of 1.
Initialize two lists, zeroLosses and oneLoss.
Iterate through the entries of the lossesCount map.
- If a player's loss count is 0, add them to the zeroLosses list.
- If a player's loss count is 1, add them to the oneLoss list.
Sort both zeroLosses and oneLoss lists in ascending order using Collections.sort().
Return a list containing the sorted zeroLosses and oneLoss lists.

Walkthrough

In this method, we use a HashMap to keep track of the number of losses for every player who has participated in at least one match. We iterate through the matches array once. For each match, we update the loss count for the loser. A key detail is to also account for players who have only won. We can do this by ensuring every winner is also present in our map, with a loss count of 0 if they haven't lost yet. After processing all matches, the map contains all players and their total losses. We then create two separate lists, one for players with zero losses and one for players with one loss, by iterating through our map. The final step is to sort these two lists as required by the problem statement.

1import java.util.*;2 3class Solution {4    public List<List<Integer>> findWinners(int[][] matches) {5        Map<Integer, Integer> lossesCount = new HashMap<>();6        7        for (int[] match : matches) {8            int winner = match[0];9            int loser = match[1];10            11            lossesCount.put(winner, lossesCount.getOrDefault(winner, 0));12            lossesCount.put(loser, lossesCount.getOrDefault(loser, 0) + 1);13        }14        15        List<Integer> zeroLosses = new ArrayList<>();16        List<Integer> oneLoss = new ArrayList<>();17        18        for (Map.Entry<Integer, Integer> entry : lossesCount.entrySet()) {19            int player = entry.getKey();20            int losses = entry.getValue();21            22            if (losses == 0) {23                zeroLosses.add(player);24            } else if (losses == 1) {25                oneLoss.add(player);26            }27        }28        29        Collections.sort(zeroLosses);30        Collections.sort(oneLoss);31        32        return Arrays.asList(zeroLosses, oneLoss);33    }34}

Complexity

Time

O(M + P log P), where M is the number of matches and P is the number of unique players. It takes O(M) to populate the HashMap. Then, it takes O(P) to iterate through the map and O(P log P) to sort the result lists. The sorting step dominates the complexity.

Space

O(P), where P is the number of unique players. This space is used to store the `lossesCount` map and the final result lists.

Trade-offs

Pros

Conceptually straightforward and easy to implement.
Flexible and works well even if player IDs are very large or not within a contiguous range, as it doesn't depend on the magnitude of the IDs.

Cons

The final sorting step (O(P log P)) makes it less efficient than approaches that can build the sorted lists directly, especially given the problem's constraints on player IDs.
HashMaps have a higher constant factor overhead compared to direct array access.

Given that player IDs are constrained to a manageable range (1 to 10^5), a more efficient approach is to use a simple array as a frequency counter. We can use the player ID as the index in the array to store their loss count. This method avoids the overhead of hashing and, more importantly, eliminates the need for a separate sorting step. By iterating through the array indices in order, we can build the result lists which will already be sorted.

Algorithm

Initialize an integer array, losses, of size 100001. To distinguish between players not seen, players with 0 losses, and players with 1+ losses, we use a state system:
- Initialize all array elements to a value indicating "not seen" (e.g., -1).
Iterate through the matches array. For each match [winner, loser]:
- For the winner: If their state is "not seen", update it to "seen with 0 losses" (e.g., set losses[winner] = 0).
- For the loser: If their state is "not seen", update it to "seen with 1 loss" (e.g., set losses[loser] = 1). Otherwise, if they have been seen before, simply increment their loss count.
Initialize two empty lists, zeroLosses and oneLoss.
Iterate through the losses array from index 1 to 100001.
- If losses[i] corresponds to the state "seen with 0 losses", add player i to zeroLosses.
- If losses[i] corresponds to the state "seen with 1 loss", add player i to oneLoss.
Since the loop iterates through player IDs in ascending order, the zeroLosses and oneLoss lists are already sorted.
Return a list containing zeroLosses and oneLoss.

Walkthrough

This approach leverages the constraint that player IDs are between 1 and 100,000. We can declare an integer array, say losses, of size 100001, where losses[i] will store information about player i. To handle all cases (player not seen, player with 0 losses, player with N losses), we can use a simple state encoding. We initialize the array with -1 to signify that no player has been seen. When we process the matches, we update the state for each winner and loser. A winner who hasn't been seen before is marked as having 0 losses. A loser's loss count is incremented. After processing all matches, we iterate through the losses array from 1 to 100001. By checking the value at each index, we can determine if the player has zero or one loss and add them to the appropriate list. This single final pass generates the lists in sorted order, making it very efficient.

1import java.util.*;2 3class Solution {4    public List<List<Integer>> findWinners(int[][] matches) {5        int[] losses = new int[100001];6        Arrays.fill(losses, -1);7 8        for (int[] match : matches) {9            int winner = match[0];10            int loser = match[1];11 12            if (losses[winner] == -1) {13                losses[winner] = 0;14            }15 16            if (losses[loser] == -1) {17                losses[loser] = 1;18            } else {19                losses[loser]++;20            }21        }22 23        List<Integer> zeroLosses = new ArrayList<>();24        List<Integer> oneLoss = new ArrayList<>();25        26        for (int i = 1; i < losses.length; i++) {27            if (losses[i] == 0) {28                zeroLosses.add(i);29            } else if (losses[i] == 1) {30                oneLoss.add(i);31            }32        }33 34        return Arrays.asList(zeroLosses, oneLoss);35    }36}

Complexity

Time

O(M + K), where M is the number of matches and K is the maximum player ID (100001). We iterate through the M matches once, and then iterate through the K possible player IDs once. This is linear time complexity.

Space

O(K), where K is the maximum player ID (100001). This space is required for the `losses` array. This is constant space with respect to the number of matches, as K is fixed by the problem constraints.

Trade-offs

Pros

Extremely efficient with a linear time complexity, making it the optimal solution for the given constraints.
Avoids the logarithmic factor of sorting or using tree-based maps.
Generates the results in sorted order naturally, simplifying the logic.

Cons

The space usage is dependent on the maximum possible player ID, not the number of actual players. This could be inefficient if the ID range were much larger and sparsely populated.

Solutions

Solution

1class Solution {2public3  List<List<Integer>> findWinners(int[][] matches) {4    Map<Integer, Integer> cnt = new HashMap<>();5    for (int[] m : matches) {6      int a = m[0], b = m[1];7      cnt.putIfAbsent(a, 0);8      cnt.put(b, cnt.getOrDefault(b, 0) + 1);9    }10    List<List<Integer>> ans = new ArrayList<>();11    ans.add(new ArrayList<>());12    ans.add(new ArrayList<>());13    for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {14      int u = entry.getKey();15      int v = entry.getValue();16      if (v < 2) {17        ans.get(v).add(u);18      }19    }20    Collections.sort(ans.get(0));21    Collections.sort(ans.get(1));22    return ans;23  }24}

1/** * @param {number[][]} matches * @return {number[][]} */ var findWinners =2  function (matches) {3    const cnt = new Map();4    for (const [a, b] of matches) {5      cnt.set(a, cnt.has(a) ? cnt.get(a) : 0);6      cnt.set(b, (cnt.get(b) || 0) + 1);7    }8    const ans = [[], []];9    for (let [u, v] of cnt.entries()) {10      if (v < 2) {11        ans[v].push(u);12      }13    }14    ans[0].sort((a, b) => a - b);15    ans[1].sort((a, b) => a - b);16    return ans;17  };

1class Solution:2    def findWinners(self, matches: List[List[int]]) -> List[List[int]]: cnt = Counter() for a, b in matches: if a not in cnt: cnt[a] = 0 cnt[b] += 1 ans = [[], []] for u, v in cnt . items(): if v < 2: ans[v]. append(u) ans[0]. sort() ans[1]. sort() return ans

1class Solution {2public:3  vector<vector<int>> findWinners(vector<vector<int>> &matches) {4    unordered_map<int, int> cnt;5    for (auto &m : matches) {6      int a = m[0], b = m[1];7      if (!cnt.count(a))8        cnt[a] = 0;9      ++cnt[b];10    }11    vector<vector<int>> ans(2);12    for (auto &[u, v] : cnt) {13      if (v < 2)14        ans[v].push_back(u);15    }16    sort(ans[0].begin(), ans[0].end());17    sort(ans[1].begin(), ans[1].end());18    return ans;19  }20};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem