Number of Good Pairs
- 1 min read
- Array
- LC-Easy
3 years ago
Solution
- Trivial solution would be O(n^2), where we'd use two for loops.
- BUT WE CAN DO BETTER!
- It doesn't matter where a certain number is, all we should care about is the frequency
- Take Example 1:
- There are three 1s.
- How many good pairs can we make from this?
- Think of the problem that Amriya made you solve
- If you have three ones, consider them as 2, because you cannot make any good pairs with the last one
- The number of good pairs you can make is 1 + 2
- If there were four ones, the answer would be 1 + 2 + 3
- Maintain a hashmap of counts, and increment the answer with the most recent count of the current character
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def numIdenticalPairs(self, nums: List[int]) -> int:
ans = 0
counts = defaultdict(lambda: 0)
for num in nums:
counts[num] += 1
if counts[num] > 1:
ans += (counts[num] - 1)
return ans