Number of Good Pairs
Problem
nums. A pair of indices
(i, j) is good when i < j and
nums[i] == nums[j]. Return how many good pairs the array contains.nums = [1,2,3,1,1,3]Output4nums = [1,1,1,1]Output6nums = [1,2,3]Output01 ≤ n ≤ 100 · 1 ≤ nums[i] ≤ 100
Try it yourself
class Solution {
public int numIdenticalPairs(int[] nums) {
}
}
k times, it forms
exactly k new good pairs (one with each earlier copy). So keep a running count
per value and add it before incrementing.Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].
Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.
Open the Hashing & Counting guide →Approaches
Brute ForceCheck Every Pair
O(n2)Space O(1)Enumerate all index pairs i < j with two nested loops and count
the ones whose values match. It is the definition turned directly into code.
public int numIdenticalPairs(int[] nums) { int pairs = 0; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] == nums[j]) pairs++; } } return pairs; }
Trivially correct and fine for n ≤ 100, but quadratic.
BetterSort, then Count Runs
O(n log n)Space O(n)After sorting a copy, equal values sit together in runs. A run of length
f contributes f·(f−1)/2 pairs, since any two of its
positions form a good pair in the original array too.
public int numIdenticalPairs(int[] nums) { int[] sorted = nums.clone(); // keep the caller's array untouched Arrays.sort(sorted); int pairs = 0; int i = 0; while (i < sorted.length) { int j = i; while (j < sorted.length && sorted[j] == sorted[i]) j++; int run = j - i; pairs += run * (run - 1) / 2; // choose 2 from the run i = j; } return pairs; }
Beats quadratic without hashing, but sorting costs a log factor and a copy.
OptimalRunning Frequency Count
O(n)Space O(V)Scan once with a frequency table (V = value range, here 101 slots).
Each new element pairs with every earlier equal element, so add
seen[x] to the answer and then bump seen[x].
public int numIdenticalPairs(int[] nums) { int[] seen = new int[101]; // values are in [1, 100] int pairs = 0; for (int x : nums) { pairs += seen[x]; // pair with each earlier copy of x seen[x]++; } return pairs; }
Dry runnums = [1,2,3,1,1,3]
- i=01i23113seen[1]=0, ans=0
- i=1,2123i113new values, ans=0
- i=31231i13seen[1]=1, ans=1
- i=412311i3seen[1]=2, ans=3
- i=5123113iseen[3]=1, ans=4 ✔
One pass, constant work per element — the standard answer.
HashMap<Integer,Integer>;
the logic is identical.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Check Every Pair | O(n2) | O(1) |
| Better | Sort, then Count Runs | O(n log n) | O(n) |
| Optimal | Running Frequency Count | O(n) | O(V) |
- Incrementing the count before adding it — counts each element pairing with itself.
- Counting ordered pairs
(i, j)and(j, i)— doubles the answer. - Using
intfor f·(f−1)/2 on huge inputs — uselongwhen n is large.
- Say the combinatorial fact out loud: a group of size f gives C(f, 2) pairs.
- Mention the incremental form: each arrival adds the number of earlier equals.
- Note the bounded value range lets you use an array instead of a hash map.