AlgoMaster Logo

Number of Good Pairs

Last Updated: March 21, 2026

easy
3 min read

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 just means we don't double-count, so each unordered pair of matching elements counts once.

The core question is: how do we efficiently count how many pairs of equal elements exist? A brute force check of every pair works, but there's a much cleaner way. If a number appears k times, the number of ways to pick 2 of those positions is k * (k - 1) / 2. That's the combination formula C(k, 2), and it's the key insight that takes us from O(n^2) to O(n).

Key Constraints:

  • nums.length <= 100 → Even O(n^2) is fast enough (at most 10,000 operations), so brute force will pass
  • nums[i] <= 100 → Values are small, meaning we could use a fixed-size array of 101 elements instead of a hash map for counting
  • nums.length >= 1 → The array is never empty, so we don't need a special empty-array check

Approach 1: Brute Force

Intuition

The most direct approach: check every possible pair (i, j) where i < j and see if nums[i] == nums[j]. If they match, increment our count. This is the "just do what the problem says" solution.

Since the array has at most 100 elements, we'll check at most about 5,000 pairs, which is nothing for a computer.

Algorithm

  1. Initialize a counter to 0
  2. For each index i from 0 to n - 2:
    • For each index j from i + 1 to n - 1:
      • If nums[i] == nums[j], increment the counter
  3. Return the counter

Example Walkthrough

1Initialize: count=0. Check all pairs (i, j) where i < j
0
1
1
2
2
3
3
1
4
1
5
3
1/7

Code

The bottleneck here is comparing every pair of elements. We don't actually care about which specific indices match, we just need to know how many times each value appears. What if we counted frequencies first and used math to compute the pairs directly?

Approach 2: Frequency Counting with Math

Intuition

Here's the key observation: good pairs are formed between elements with the same value. So the problem reduces to: for each distinct value, how many pairs can we form from its occurrences?

If the number 3 appears at indices 2 and 5, that's 1 pair. If 1 appears at indices 0, 3, and 4, that's 3 pairs: (0,3), (0,4), (3,4). See the pattern? If a value appears k times, the number of good pairs from that value is C(k, 2) = k * (k - 1) / 2.

So the algorithm is: count how often each number appears, then sum up C(k, 2) for each frequency.

Algorithm

  1. Count the frequency of each number using a hash map (or fixed-size array since values are at most 100)
  2. For each frequency k in the map, add k * (k - 1) / 2 to the result
  3. Return the total

Example Walkthrough

1Start: count frequencies of each value
0
1
1
2
2
3
3
1
4
1
5
3
1/5

Code

The two-pass approach is already O(n), but it requires two separate loops. Can we compute the answer in a single pass through the array, accumulating pairs as we go?

Approach 3: Single-Pass Counting

Intuition

Instead of counting all frequencies first and then computing pairs, we can do both at once. As we iterate through the array, we maintain a running count of how many times we've seen each number so far. When we encounter a number that's already appeared c times, it forms c new good pairs (one with each previous occurrence). We add c to our result and then increment the count.

This is a common trick in counting problems: rather than computing C(k, 2) after the fact, we accumulate pairs incrementally. The math works out the same, since 0 + 1 + 2 + ... + (k-1) = k * (k - 1) / 2.

Algorithm

  1. Initialize a frequency map (or array) and a counter to 0
  2. For each number in the array:
    • Add its current frequency to the counter (this many new pairs are formed)
    • Increment its frequency by 1
  3. Return the counter

Example Walkthrough

1Initialize: freq={}, count=0
0
1
1
2
2
3
3
1
4
1
5
3
1/8

Code