Number of Good Pairs

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

Given a list of numbers, return number of pairs that aren't the same index and index of j from (i, j) is j > i

Why This Works

(Explain the core reason the solution is correct.)

Here’s the clean math behind LeetCode 1512: Number of Good Pairs.

The formula

If a value appears c times in the array, it contributes

(\binom{c}{2}) = \frac{c (c - 1)}{2}

good pairs.
So the total number of good pairs is

\sum_{v} (\binom{c_{v}}{2}) = \sum_{v} \frac{c_{v} (c_{v} - 1)}{2},

where $c_{v}$ is the count of value $v$ .

Why it works (two easy views)

Combinatorial (choose 2 indices):
For any fixed value $v$ with $c$ occurrences, a “good pair” is just choosing 2 distinct indices among those $c$ . The number of ways to choose 2 items from $c$ is $(\binom{c}{2})$ . Summing over values gives the total.
Ordered-to-unordered (double counting):
Among the $c$ equal elements, there are $c (c - 1)$ ordered pairs $(i, j)$ with $i \neq j$ . But each unordered pair ${i, j}$ appears twice (once as $(i, j)$ and once as $(j, i)$ ). Restricting to $i < j$ divides by 2, giving $c (c - 1) / 2$ .

Tiny example

nums = [1,1,1,2,2,3]
Counts: $c_{1} = 3, c_{2} = 2, c_{3} = 1$ .
Pairs = $(\binom{3}{2}) + (\binom{2}{2}) + (\binom{1}{2}) = 3 + 1 + 0 = 4$ .
(The pairs are (0,1), (0,2), (1,2) for 1’s, and (3,4) for 2’s.)

Notes / edges

If $c \leq 1$ , $(\binom{c}{2}) = 0$ (no pair possible).
Implementation-wise: count frequencies with a hash map, then sum $c (c - 1) / 2$ over all counts. Time $O (n)$ , space up to number of distinct values.

That’s it—the $(\binom{c}{2})$ piece is the whole trick.

Main Concepts Used

(Mark the CS concepts or algorithms used.)

Time & Space Complexity

Time: $O ()$ → Reason:
Space: $O ()$ → Reason:

Intuitive Code

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        hashmap = {}
        for i, num in enumerate(nums):
            hashmap[num] = hashmap.get(num, [])
            hashmap[num].append(i)
        
        result = 0
        for indices in hashmap.values():
            if len(indices) < 2:
                continue
            for i, index in enumerate(indices):
                result += len(indices) - i - 1
        
        return result

Optimized Code

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        hashmap = {}
        for i, num in enumerate(nums):
            hashmap[num] = hashmap.get(num, 0) + 1

        result = 0
        for num in hashmap.keys():
            count = hashmap[num]
            goodPairs = (count * (count - 1)) // 2
            result += goodPairs
        
        return result

Common Mistakes / Things I Got Stuck On

Not using integer division
Iterating over nums again which has duplicates