Number of Good Pairs LeetCode 1512

LeetCode 1512 — Number of Good Pairs — gives you an array of integers nums and asks you to return the number of good pairs. A pair (i, j) is considered good if nums[i] == nums[j] and i < j. The indices must be distinct and i must be strictly less than j — so you are counting ordered pairs where the smaller index comes first.

For example, given nums = [1, 2, 3, 1, 1, 3], the answer is 4. The good pairs are: (0,3), (0,4), (3,4) — the three pairs among the three 1s — and (2,5) — the one pair between the two 3s. The single 2 forms no pairs.

This is an Easy-rated problem but it introduces a foundational pattern: instead of iterating all pairs with a nested loop, count value frequencies and apply combinatorics to derive the answer in linear time.

The straightforward solution uses two nested loops: for each index i, scan all indices j > i and check if nums[i] == nums[j]. Every matching pair increments a counter. This is O(n^2) time and O(1) space. For the given constraint of n <= 100, this runs in at most 4,950 comparisons — well within limits.

The brute force is correct and simple to implement, but it misses a key mathematical insight that makes the problem much more elegant. When you find three 1s in the array, you are not just lucky — you know immediately that they form exactly 3 pairs without checking each one individually.

The brute force teaches you what you are counting. The optimized approach teaches you how to count it smarter.

The optimal solution builds a frequency map of each value in nums. For each value v with frequency k, compute k*(k-1)/2 and add it to the running total. This is because choosing any 2 indices from k equal elements gives one valid good pair — and the number of ways to choose 2 items from k is the combination C(k,2) = k*(k-1)/2.

The implementation is clean: one pass to build the frequency map using a HashMap or Counter, then one pass over the map entries to apply the formula. Total time is O(n) for counting plus O(u) for summing where u is the number of unique values — overall O(n). Space is O(u) for the map.

This approach scales to arbitrarily large arrays where the brute force would time out. For nums.length = 10^5 and all identical elements, brute force does ~5 billion operations; the frequency approach does exactly 1 formula evaluation.

The formula k*(k-1)/2 is the combination C(k, 2) — the number of ways to choose 2 items from k items without regard to order. Since every pair of indices (i, j) with i < j and nums[i] == nums[j] is a good pair, and since we want unordered pairs (only i < j, not both orderings), we need exactly C(k, 2) per value group.

Formally: C(k, 2) = k! / (2! * (k-2)!) = k*(k-1)/2. For frequency 3: 3*2/2 = 3 pairs. For frequency 4: 4*3/2 = 6 pairs. For frequency 5: 5*4/2 = 10 pairs. You can verify: four 1s at positions 0,1,2,3 form pairs (0,1),(0,2),(0,3),(1,2),(1,3),(2,3) — exactly 6.

The formula increments quadratically with frequency, which is why detecting high-frequency values and applying the formula is so much more efficient than enumerating pairs individually.

There is an elegant alternative that avoids the combination formula entirely: the online counting approach. Iterate through the array; for each element, look up how many times that value has already appeared (its current count in the map), and add that count directly to the result. Then increment the count. This works because each new occurrence pairs with every previous occurrence of the same value.

For example, processing [1, 1, 1]: first 1 — count[1]=0, add 0, count[1] becomes 1. Second 1 — count[1]=1, add 1, count[1] becomes 2. Third 1 — count[1]=2, add 2, count[1] becomes 3. Total: 0+1+2 = 3 = C(3,2). The result is identical to the formula approach but derived step by step.

The online approach naturally enforces the i < j constraint: when processing element at index j, count[v] holds only the number of occurrences before j, so every counted pairing has a smaller index on the left. No formula required, no two-pass algorithm needed.

Python one-liner using Counter and the formula: from collections import Counter; return sum(k*(k-1)//2 for k in Counter(nums).values()). This is concise and idiomatic. The online version with defaultdict: count = defaultdict(int); result = 0; for v in nums: result += count[v]; count[v] += 1; return result. Both are O(n) time and O(n) space.

Java formula approach: Map<Integer,Integer> freq = new HashMap<>(); for (int v : nums) freq.merge(v, 1, Integer::sum); int res = 0; for (int k : freq.values()) res += k*(k-1)/2; return res. Java online approach: Map<Integer,Integer> cnt = new HashMap<>(); int res = 0; for (int v : nums) { res += cnt.getOrDefault(v,0); cnt.merge(v,1,Integer::sum); } return res.

Both languages achieve O(n) time and O(u) space where u is the number of unique values. In the worst case u = n (all distinct, zero good pairs). In the best case u = 1 (all identical, n*(n-1)/2 good pairs). The space overhead from the HashMap is always bounded by the input size.

Number of Good Pairs belongs to the frequency-counting and pair-detection family. Contains Duplicate (LeetCode 217) is the simplest relative: does any value appear more than once? It uses the same frequency map but only needs to detect k >= 2, not count pairs. Two Sum (LeetCode 1) also uses a hash map for O(n) lookup but targets a specific sum rather than equality.

Valid Anagram (LeetCode 242) uses frequency counting on character arrays — same HashMap pattern applied to strings. The pair-counting family extends further: Number of Equivalent Domino Pairs (LeetCode 1128) applies the same nC2 formula to pairs of dominoes; Find the Number of Good Pairs II (LeetCode 3162) adds divisibility constraints on top of the matching condition.

The combination formula k*(k-1)/2 is the thread connecting all these problems. Whenever you count unordered pairs within a group of k equal or equivalent items, nC2 is the answer. Mastering this pattern on LeetCode 1512 pays dividends across the entire counting and hashmap problem category.