Number of Good Pairs — Solution in Python, Java & C++
Number of Good Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Number of Good Pairs is an easy coding problem on arrays, hash table and math, asked in Amazon, Adobe and Cognizant interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Math, Counting
- Asked at: Amazon, Adobe, Cognizant
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of integers nums, a pair (i, j) is good if nums[i] == nums[j] and i < j.
Return the number of good pairs.
Example 1
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: The good pairs are (0,3), (0,4), (3,4) and (2,5).
Example 2
Input: nums = [1,1,1,1]
Output: 6
Explanation: Every one of the 4-choose-2 pairs qualifies.
Example 3
Input: nums = [1,2,3]
Output: 0
Constraints
1 <= nums.length <= 401 <= nums[i] <= 100
Hints for Number of Good Pairs
Hint 1
A value seen
ctimes contributesc × (c - 1) / 2pairs.Hint 2
Or count as you scan: each new occurrence pairs with every earlier occurrence of the same value.
How to solve Number of Good Pairs
Each new occurrence of a value pairs with every earlier occurrence, so add the running count of that value before incrementing it.
Approach
- Keep
count[value]. - For each
x, addcount[x]to the answer, then incrementcount[x].
Why it works
Summing the pre-increment counts over all occurrences of a value with total frequency c gives 0 + 1 + … + (c - 1) = c(c - 1)/2, the number of unordered pairs.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Incrementing before adding double-counts each element with itself.
Reference solution
Python
def numIdenticalPairs(nums):
count = {}
total = 0
for x in nums:
total += count.get(x, 0)
count[x] = count.get(x, 0) + 1
return totalJava
public static int numIdenticalPairs(int[] nums) {
Map<Integer, Integer> count = new HashMap<>();
int total = 0;
for (int x : nums) {
int seen = count.getOrDefault(x, 0);
total += seen;
count.put(x, seen + 1);
}
return total;
}C++
int numIdenticalPairs(vector<int>& nums) {
unordered_map<int, int> count;
int total = 0;
for (int x : nums) {
total += count[x];
count[x]++;
}
return total;
}JavaScript
var numIdenticalPairs = function(nums) {
const count = new Map();
let total = 0;
for (let i = 0; i < nums.length; i++) {
const seen = count.get(nums[i]) || 0;
total += seen;
count.set(nums[i], seen + 1);
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets