LeetCode 2225. Find Players With Zero or One Losses Solution in Java, C++, Python & More | Explanation + Code

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.

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.

Solutions

Solution 1: Hash Table + Sorting

We use a hash table cnt to record the number of matches each player has lost.

Then we traverse the hash table, put the players who lost 0 matches into ans[0], and put the players who lost 1 match into ans[1].

Finally, we sort ans[0] and ans[1] in ascending order and return the result.

The time complexity is O(n × log n), and the space complexity is O(n). Where n is the number of matches.

PythonJavaC++GoTypeScriptJavaScript

class Solution: def findWinners(self, matches: List[List[int]]) -> List[List[int]]: cnt = Counter() for winner, loser in matches: if winner not in cnt: cnt[winner] = 0 cnt[loser] += 1 ans = [[], []] for x, v in sorted(cnt.items()): if v < 2: ans[v].append(x) return ans(code-box)

class Solution { public List<List<Integer>> findWinners(int[][] matches) { Map<Integer, Integer> cnt = new HashMap<>(); for (var e : matches) { cnt.putIfAbsent(e[0], 0); cnt.merge(e[1], 1, Integer::sum); } List<List<Integer>> ans = List.of(new ArrayList<>(), new ArrayList<>()); for (var e : cnt.entrySet()) { if (e.getValue() < 2) { ans.get(e.getValue()).add(e.getKey()); } } Collections.sort(ans.get(0)); Collections.sort(ans.get(1)); return ans; } }(code-box)

class Solution { public: vector<vector<int>> findWinners(vector<vector<int>>& matches) { map<int, int> cnt; for (auto& e : matches) { if (!cnt.contains(e[0])) { cnt[e[0]] = 0; } ++cnt[e[1]]; } vector<vector<int>> ans(2); for (auto& [x, v] : cnt) { if (v < 2) { ans[v].push_back(x); } } return ans; } };(code-box)

func findWinners(matches [][]int) [][]int { cnt := map[int]int{} for _, e := range matches { if _, ok := cnt[e[0]]; !ok { cnt[e[0]] = 0 } cnt[e[1]]++ } ans := make([][]int, 2) for x, v := range cnt { if v < 2 { ans[v] = append(ans[v], x) } } sort.Ints(ans[0]) sort.Ints(ans[1]) return ans }(code-box)

function findWinners(matches: number[][]): number[][] { const cnt: Map<number, number> = new Map(); for (const [winner, loser] of matches) { if (!cnt.has(winner)) { cnt.set(winner, 0); } cnt.set(loser, (cnt.get(loser) || 0) + 1); } const ans: number[][] = [[], []]; for (const [x, v] of cnt) { if (v < 2) { ans[v].push(x); } } ans[0].sort((a, b) => a - b); ans[1].sort((a, b) => a - b); return ans; }(code-box)

/** * @param {number[][]} matches * @return {number[][]} */ var findWinners = function (matches) { const cnt = new Map(); for (const [winner, loser] of matches) { if (!cnt.has(winner)) { cnt.set(winner, 0); } cnt.set(loser, (cnt.get(loser) || 0) + 1); } const ans = [[], []]; for (const [x, v] of cnt) { if (v < 2) { ans[v].push(x); } } ans[0].sort((a, b) => a - b); ans[1].sort((a, b) => a - b); return ans; };(code-box)