Difficulty: Easy | Acceptance: 89.80% | Paid: No Topics: Array, Hash Table, Math, Counting
Given an array of integers nums, a pair (i, j) is called good if nums[i] == nums[j] and i < j.
Return the number of good pairs.
- Examples
- Constraints
- Brute Force
- Hash Map Counting
- Mathematical Formula
Examples
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair (i,j) with i < j is a good pair.
Input: nums = [1,2,3]
Output: 0
Constraints
1 <= nums.length <= 100
1 <= nums[i] <= 100
Brute Force
Intuition Check every possible pair of indices and count those where values match and the first index is smaller.
Steps
- Initialize count to 0
- Use nested loops to compare each element with all elements after it
- Increment count when values match
python
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
count = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
count += 1
return count
Complexity
- Time: O(n²)
- Space: O(1)
- Notes: Simple but inefficient for large arrays
Hash Map Counting
Intuition Track the frequency of each number seen so far. Each time we encounter a number, it forms good pairs with all previous occurrences of that number.
Steps
- Create a hash map to store frequency of each number
- For each number in the array, add its current frequency to the count
- Increment the frequency in the map
python
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
count = 0
freq = {}
for num in nums:
if num in freq:
count += freq[num]
freq[num] += 1
else:
freq[num] = 1
return count
Complexity
- Time: O(n)
- Space: O(n)
- Notes: Optimal single-pass solution
Mathematical Formula
Intuition If a number appears k times, it contributes k*(k-1)/2 good pairs (combination formula C(k,2)). Sum this for all unique numbers.
Steps
- Count frequency of each number using a hash map
- For each frequency value, compute pairs using formula k*(k-1)/2
- Sum all pairs to get the total
python
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
from collections import Counter
freq = Counter(nums)
count = 0
for v in freq.values():
count += v * (v - 1) // 2
return count
Complexity
- Time: O(n)
- Space: O(n)
- Notes: Elegant mathematical approach, same complexity as hash map counting