Number of Good Pairs

TARGET DECK: Leetcode FILE TAGS:

Intuition

START Basic Front: Number of Good Pairs Back: You can convert this into a mathematical formula from 0 to n - 1 Tags:

END

Complexity

Runtime

$O(N)$

Space

$O(N)$ due to hashmap

Code

One Liner

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        return sum(val * (val - 1) // 2 for val in Counter(nums).values())

Hashmap

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        hm = defaultdict(int)
        for i, num in enumerate(nums):
            hm[num] += 1
        
 
        return sum(val * (val - 1) // 2 for val in hm.values())

Two For Loops

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        hm = defaultdict(int)
        for i, num in enumerate(nums):
            hm[num] += 1
        
        for num in hm:
            for i in range(hm[num] - 1, 0, -1):
                count += i
        
        return count

Brute Force

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j]:
                    count += 1
        
        return count

Notes

---

References

https://leetcode.com/problems/number-of-good-pairs/