Skip to content

2225. Find Players With Zero or One Losses 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  vector<vector<int>> findWinners(vector<vector<int>>& matches) {
    vector<vector<int>> ans(2);
    map<int, int> lossesCount;

    for (const vector<int>& m : matches) {
      const int winner = m[0];
      const int loser = m[1];
      if (!lossesCount.count(winner))
        lossesCount[winner] = 0;
      ++lossesCount[loser];
    }

    for (const auto& [player, nLosses] : lossesCount)
      if (nLosses < 2)
        ans[nLosses].push_back(player);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public List<List<Integer>> findWinners(int[][] matches) {
    List<List<Integer>> ans = Arrays.asList(new ArrayList<>(), new ArrayList<>());
    Map<Integer, Integer> lossesCount = new TreeMap<>();

    for (int[] m : matches) {
      final int winner = m[0];
      final int loser = m[1];
      if (!lossesCount.containsKey(winner))
        lossesCount.put(winner, 0);
      lossesCount.merge(loser, 1, Integer::sum);
    }

    for (final int player : lossesCount.keySet()) {
      final int nLosses = lossesCount.get(player);
      if (nLosses < 2)
        ans.get(nLosses).add(player);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
    ans = [[] for _ in range(2)]
    lossesCount = collections.Counter()

    for winner, loser in matches:
      if winner not in lossesCount:
        lossesCount[winner] = 0
      lossesCount[loser] += 1

    for player, nLosses in lossesCount.items():
      if nLosses < 2:
        ans[nLosses].append(player)

    return [sorted(ans[0]), sorted(ans[1])]