Sponsored
Sponsored
This approach involves using hash maps (or dictionaries) to track the number of matches each player has won and lost. We loop over the matches to populate these maps. Finally, we iterate over the accumulated data to build the two result lists: players with zero losses and players with exactly one loss. We then sort these lists before returning them.
Time Complexity: O(n log n) due to the sorting of players.
Space Complexity: O(n) for storing player and loss information.
1def findWinners(matches):
2 from collections import defaultdict
3 losses_count = defaultdict(int)
4 players = set()
5 for winner, loser in matches:
6 players.add(winner)
7 players.add(loser)
8 losses_count[loser] += 1
9 zero_losses = [player for player in players if losses_count[player] == 0]
10 one_loss = [player for player in players if losses_count[player] == 1]
11 return [sorted(zero_losses), sorted(one_loss)]We use a dictionary to count the number of losses for each player. We also maintain a set of all players to ensure that we consider only those who have played matches. By checking the dictionary, we categorize players into those with zero and one loss, sort them, and return the result.
In this approach, we maintain two numerical arrays or lists: one to track whether a player has won, and another to count how many times a player has lost. We then deduce the needed lists by examining these arrays.
Time Complexity: O(n log n)
Space Complexity: O(n)
1#include <vector>
2#include <algorithm>
3using namespace std;
4vector<vector<int>> findWinners(vector<vector<int>>& matches) {
5 vector<int> losses(100001, 0), played(100001, 0);
for (auto& match : matches) {
played[match[0]] = 1;
played[match[1]] = 1;
losses[match[1]]++;
}
vector<int> noLosses, oneLoss;
for (int i = 1; i <= 100000; ++i) {
if (played[i]) {
if (losses[i] == 0) noLosses.push_back(i);
else if (losses[i] == 1) oneLoss.push_back(i);
}
}
return {noLosses, oneLoss};
}Using two arrays of size 100,001 ensures constant time access for any player index. The 'losses' array stores the count of losses for each player, and the 'played' array indicates whether a player has participated. Finally, we evaluate these arrays to find and sort players with zero or one loss.