Number of Good Pairs
Understanding the Problem
We need to count pairs of indices (i, j) where i < j and both positions hold the same value. The i < j constraint prevents double-counting, so each unordered pair of matching elements counts once.
The core question is how to count pairs of equal elements without comparing every pair. A brute force check of all pairs works, but there is a faster route. If a number appears k times, the number of ways to pick 2 of those positions is k * (k - 1) / 2, the combination formula C(k, 2). Counting frequencies and applying this formula turns an O(n^2) scan into O(n).
Key Constraints:
nums.length <= 100→ Even O(n^2) stays under 10,000 operations, so brute force passes within limitsnums[i] <= 100→ Values fit in a fixed-size array of 101 elements, which is faster than a hash map for countingnums.length >= 1→ The array is never empty, so no empty-input check is needed
Approach 1: Brute Force
Intuition
Check every pair of indices (i, j) where i < j. If nums[i] == nums[j], the pair is good, so increment the count. This follows the definition directly.
With at most 100 elements, the inner and outer loops together examine at most n * (n - 1) / 2 = 4,950 pairs, which runs instantly.
Algorithm
- Initialize a counter to 0
- For each index
ifrom 0 ton - 2: - For each index
jfromi + 1ton - 1: - If
nums[i] == nums[j], increment the counter - Return the counter
Example Walkthrough
Code
- Time Complexity: O(n^2). We check every pair of elements. The outer loop runs n times, and for each iteration, the inner loop runs up to n - 1 times. Total comparisons: n * (n - 1) / 2.
- Space Complexity: O(1). We only use a single counter variable, no extra data structures.
The bottleneck is comparing every pair of elements. The specific indices that match don't matter, only how many times each value appears. The next approach counts frequencies first and computes the pairs with arithmetic.
Approach 2: Frequency Counting with Math
Intuition
Good pairs form between elements that share the same value, so the problem splits by value: for each distinct value, count the pairs among its occurrences.
If the number 3 appears at indices 2 and 5, that is 1 pair. If 1 appears at indices 0, 3, and 4, that is 3 pairs: (0,3), (0,4), (3,4). When a value appears k times, the number of good pairs from that value is C(k, 2) = k * (k - 1) / 2.
The algorithm counts how often each number appears, then sums C(k, 2) over all frequencies.
Two positions form a good pair exactly when they hold the same value, and the i < j rule counts each such unordered position pair once. For a value occurring k times, the number of unordered pairs of its positions is C(k, 2) = k * (k - 1) / 2. Pairs from different values never coincide because the values differ, so summing C(k, 2) over all values counts every good pair once with no overlap.
Algorithm
- Count the frequency of each number using a hash map (or fixed-size array since values are at most 100)
- For each frequency
kin the map, addk * (k - 1) / 2to the result - Return the total
Example Walkthrough
Code
- Time Complexity: O(n). One pass to count frequencies, then one pass over the frequency map (at most 100 entries given the constraints). Both are linear.
- Space Complexity: O(1). The frequency array has a fixed size of 101 regardless of input size. If values could be arbitrary, this would be O(k) where k is the number of distinct values.
This approach is O(n) but makes two passes: one to count frequencies and one to sum the pairs. The next approach folds both into a single pass that accumulates pairs while counting.
Approach 3: Single-Pass Counting
Intuition
Count frequencies and accumulate pairs in the same pass. While iterating, keep a running count of how many times each number has appeared so far. When the current number has already appeared c times, it forms c new good pairs, one with each previous occurrence. Add c to the result, then increment the count for that number.
Accumulating pairs incrementally produces the same total as computing C(k, 2) afterward, because the new pairs added across the k occurrences of a value are 0 + 1 + 2 + ... + (k - 1), which equals k * (k - 1) / 2.
Algorithm
- Initialize a frequency map (or array) and a counter to 0
- For each number in the array:
- Add its current frequency to the counter (this many new pairs are formed)
- Increment its frequency by 1
- Return the counter
Example Walkthrough
Code
- Time Complexity: O(n). Single pass through the array. Each element requires O(1) work (array lookup and increment).
- Space Complexity: O(1). Fixed-size array of 101 elements. With arbitrary values, it would be O(k) where k is the number of distinct values.