MediumNo. 2225
Find Players With Zero or One Losses — LeetCode 2225 Python Solution
- Pattern
- Sorting
- Topics
- Array, Hash Table, Counting, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The 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.
Example
- 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.
Python solution
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 ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2225. Find Players With Zero or One Losses is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0169 | Majority Element | Easy |
| 0229 | Majority Element II | Medium |
| 0347 | Top K Frequent Elements | Medium |
| 0594 | Longest Harmonious Subsequence | Easy |
| 0621 | Task Scheduler | Medium |
| 0692 | Top K Frequent Words | Medium |
Frequently asked questions
- How hard is LeetCode 2225. Find Players With Zero or One Losses?
LeetCode 2225. Find Players With Zero or One Losses is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2225. Find Players With Zero or One Losses?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 2225. Find Players With Zero or One Losses?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2225. Find Players With Zero or One Losses cover?
LeetCode 2225. Find Players With Zero or One Losses is tagged Array, Hash Table, Counting and Sorting on LeetCode.