Number of Good Pairs

Number of Good Pairs

What is this problem about?

The Number of Good Pairs problem asks you to count the number of pairs (i, j) where i < j and arr[i] == arr[j]. This Number of Good Pairs coding problem has a clean O(n) solution using frequency counting and the combination formula.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, Bloomberg, and many others ask this as a quick screening problem that verifies hash map and combination counting skills. The array, math, hash table, and counting interview pattern is demonstrated at its most fundamental level.

Algorithmic pattern used

Frequency count + running combination. For each element value, track its frequency so far. When element x is seen for the f-th time, it can pair with all f-1 previous occurrences → add f-1 to the result. This gives the count incrementally without a separate combination formula step.

Example explanation

Array: [1,2,3,1,1,3].

• See 1 (first time): freq[1]=1. Add 0.
• See 2: freq[2]=1. Add 0.
• See 3: freq[3]=1. Add 0.
• See 1 (second time): freq[1]=2. Add 1.
• See 1 (third time): freq[1]=3. Add 2.
• See 3 (second time): freq[3]=2. Add 1. Total = 0+0+0+1+2+1 = 4.

Common mistakes candidates make

• Using nested loops O(n²) when O(n) is straightforward.
• Computing C(freq,2) at the end instead of incrementally (both work but incremental is cleaner).
• Not initializing the frequency map.
• Off-by-one: add freq-1 (not freq) when seeing the element for the freq-th time.

Interview preparation tip

Good Pairs is the canonical "count pairs with equal values" problem. The incremental counting trick — add (current_freq - 1) when each element is seen — is O(n) and avoids a second pass. This same technique applies to "count pairs with sum k" (use complement hash map) and other pair-counting problems. Memorize the pattern: process elements left to right, for each element query the map for how many valid partners already exist, then update the map.