Problem Statement
leetcode problem link
My Solution [Accepted]
class Solution:
def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
res = [[], []]
winner_cnt = Counter()
loser_cnt = Counter()
for winner, loser in matches:
winner_cnt[winner] += 1
loser_cnt[loser] -= 1
if loser in winner_cnt:
del winner_cnt[loser]
if winner in loser_cnt:
del winner_cnt[winner]
res[0] = sorted(list(winner_cnt.keys()))
res[1] = sorted([player for player, cnt in loser_cnt.items() if cnt == -1])
return res
Editorial
Approach 1: Hash Set
class Solution:
def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
zero_loss = set()
one_loss = set()
more_losses = set()
for winner, loser in matches:
# Add winner
if (winner not in one_loss) and (winner not in more_losses):
zero_loss.add(winner)
# Add or move loser.
if loser in zero_loss:
zero_loss.remove(loser)
one_loss.add(loser)
elif loser in one_loss:
one_loss.remove(loser)
more_losses.add(loser)
elif loser in more_losses:
continue
else:
one_loss.add(loser)
return [sorted(list(zero_loss)), sorted(list(one_loss))]
Approach 2: Hash Set + Hash Map
class Solution:
def findWinners(self, matches : List[List[int]]) ->List[List[int]]:
seen = set() losses_count = {}
for winner, loser in matches:
seen.add(winner)
seen.add(loser)
losses_count[loser] = losses_count.get(loser, 0) + 1
# Add players with 0 or 1 loss to the corresponding list.
zero_lose, one_lose = [], []
for player in seen:
count = losses_count.get(player, 0)
if count == 0:
zero_lose.append(player)
elif count == 1:
one_lose.append(player)
return [sorted(zero_lose), sorted(one_lose)]
