# Find Players With Zero or One Losses **Difficulty:** MEDIUM [External](https://leetcode.com/problems/find-players-with-zero-or-one-losses) Canonical: https://scaleengineer.com/dsa/problems/find-players-with-zero-or-one-losses **Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting) **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array, Hash Table **Companies:** [Indeed](https://scaleengineer.com/companies/indeed), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies) --- ## Problem 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**. # Approaches ## HashMap to Count Losses and Sorting 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. **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. **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. ### Explanation 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. ```java import java.util.*; class Solution { public List> findWinners(int[][] matches) { Map lossesCount = new HashMap<>(); for (int[] match : matches) { int winner = match[0]; int loser = match[1]; lossesCount.put(winner, lossesCount.getOrDefault(winner, 0)); lossesCount.put(loser, lossesCount.getOrDefault(loser, 0) + 1); } List zeroLosses = new ArrayList<>(); List oneLoss = new ArrayList<>(); for (Map.Entry entry : lossesCount.entrySet()) { int player = entry.getKey(); int losses = entry.getValue(); if (losses == 0) { zeroLosses.add(player); } else if (losses == 1) { oneLoss.add(player); } } Collections.sort(zeroLosses); Collections.sort(oneLoss); return Arrays.asList(zeroLosses, oneLoss); } } ``` ### Algorithm * Initialize a `HashMap` 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. ## Efficient Counting with a Frequency Array 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. **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. **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. ### Explanation 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. ```java import java.util.*; class Solution { public List> findWinners(int[][] matches) { int[] losses = new int[100001]; Arrays.fill(losses, -1); for (int[] match : matches) { int winner = match[0]; int loser = match[1]; if (losses[winner] == -1) { losses[winner] = 0; } if (losses[loser] == -1) { losses[loser] = 1; } else { losses[loser]++; } } List zeroLosses = new ArrayList<>(); List oneLoss = new ArrayList<>(); for (int i = 1; i < losses.length; i++) { if (losses[i] == 0) { zeroLosses.add(i); } else if (losses[i] == 1) { oneLoss.add(i); } } return Arrays.asList(zeroLosses, oneLoss); } } ``` ### 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`. # Solutions ### Java ```java class Solution { public List> findWinners(int[][] matches) { Map cnt = new HashMap<>(); for (int[] m : matches) { int a = m[0], b = m[1]; cnt.putIfAbsent(a, 0); cnt.put(b, cnt.getOrDefault(b, 0) + 1); } List> ans = new ArrayList<>(); ans.add(new ArrayList<>()); ans.add(new ArrayList<>()); for (Map.Entry entry : cnt.entrySet()) { int u = entry.getKey(); int v = entry.getValue(); if (v < 2) { ans.get(v).add(u); } } Collections.sort(ans.get(0)); Collections.sort(ans.get(1)); return ans; } } ``` ### JavaScript ```javascript /** * @param {number[][]} matches * @return {number[][]} */ var findWinners = function (matches) { const cnt = new Map(); for (const [a, b] of matches) { cnt.set(a, cnt.has(a) ? cnt.get(a) : 0); cnt.set(b, (cnt.get(b) || 0) + 1); } const ans = [[], []]; for (let [u, v] of cnt.entries()) { if (v < 2) { ans[v].push(u); } } ans[0].sort((a, b) => a - b); ans[1].sort((a, b) => a - b); return ans; }; ``` ### Python ```python class Solution: 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 ``` ### CPP ```cpp class Solution { public: vector> findWinners(vector> &matches) { unordered_map cnt; for (auto &m : matches) { int a = m[0], b = m[1]; if (!cnt.count(a)) cnt[a] = 0; ++cnt[b]; } vector> ans(2); for (auto &[u, v] : cnt) { if (v < 2) ans[v].push_back(u); } sort(ans[0].begin(), ans[0].end()); sort(ans[1].begin(), ans[1].end()); return ans; } }; ```