1512. Number of Good Pairs
Model: qwen2.5-coder:14b
Topics: Array,Hash Table,Math
FAANG asked: 1
Acceptance rate: 87.7%
Problem Breakdown
The problem asks us to find the number of “good pairs” in an array of integers nums. A pair (i, j) is considered good if:
nums[i] == nums[j]i < j
Inputs:
- An array of integers
numswhere1 <= nums.length <= 100and1 <= nums[i] <= 100.
Outputs:
- An integer representing the number of good pairs.
Implicit Constraints or Edge Cases:
- The array can contain duplicate values.
- The array length is small enough to allow for efficient computation.
- All elements are positive integers within a specific range, which simplifies certain data structures we might use.
Intuition
A brute-force approach would involve checking every possible pair (i, j) where i < j and counting those that satisfy the condition nums[i] == nums[j]. This approach has a time complexity of (O(n^2)), which is inefficient given the constraints.
The key insight to improve this solution is to recognize that if we know how many times each number appears in the array, we can calculate the number of good pairs directly using combinatorial mathematics. Specifically, for a number that appears count times, the number of ways to choose 2 items from these count items (i.e., the number of good pairs) is given by the combination formula (C(count, 2) = \frac{count \times (count - 1)}{2}).
Approach
- Count Occurrences: Use a hash table (dictionary in Python) to count how many times each number appears in the array.
- Calculate Good Pairs: For each unique number in the hash table, use the combination formula to calculate the number of good pairs and accumulate this value.
Data Structures:
- A dictionary to store the frequency of each number in
nums.
Complexity Analysis
- Time Complexity: (O(n)), where (n) is the length of the array. We make a single pass through the array to count occurrences and another pass through the unique numbers to calculate good pairs.
- Space Complexity: (O(k)), where (k) is the number of unique numbers in
nums. In the worst case, this could be (O(n)) if all numbers are unique.
Solution
def numIdenticalPairs(nums):
# Step 1: Count occurrences of each number
count = {}
for num in nums:
if num in count:
count[num] += 1
else:
count[num] = 1
# Step 2: Calculate the number of good pairs
good_pairs = 0
for cnt in count.values():
if cnt > 1:
good_pairs += (cnt * (cnt - 1)) // 2
return good_pairs
# Example usage:
print(numIdenticalPairs([1,2,3,1,1,3])) # Output: 4
print(numIdenticalPairs([1,1,1,1])) # Output: 6
print(numIdenticalPairs([1,2,3])) # Output: 0
Edge Cases Handled
- All unique numbers: If all numbers are unique, the dictionary will have an entry for each number with a count of 1. The combination formula (C(1, 2)) results in 0 good pairs.
- All identical numbers: If all numbers are the same, the dictionary will have one entry with a count equal to the length of the array. The combination formula will correctly compute the total number of pairs.
- Empty input: Although not explicitly mentioned in constraints, if
numsis empty, the function will return 0 as expected since there are no pairs to consider.
The solution provided is correct and efficient, adhering to the problem constraints and handling all edge cases appropriately.