# The Pair Counter

> How many pairs can be formed from the crowd?

Canonical URL: <https://datadriven.io/problems/the_pair_counter>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given a list of integers, return the number of index pairs (i, j) with i < j and nums[i] == nums[j].

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **counting pairs using frequency analysis** instead of brute-force nested loops. It checks whether candidates can derive the pair count from value frequencies using combinatorics (n choose 2).

> **Trick to Solving**
>
> Count the frequency of each value. For a value appearing k times, the number of pairs is `k * (k - 1) / 2`. Sum this across all values. This avoids O(n^2) comparison of all pairs.

---

### Break down the requirements

#### Step 1: Count the frequency of each value

Build a dictionary mapping each integer to its occurrence count.

#### Step 2: Compute pairs from each frequency

For each value with count k, the number of valid index pairs is `k * (k - 1) // 2`.

#### Step 3: Sum all pair counts

Add up the pair counts across all values.

---

### The solution

**Frequency-based pair counting with nC2**

```python
def count_pairs(nums):
    freq = {}
    for num in nums:
        if num in freq:
            freq[num] += 1
        else:
            freq[num] = 1
    total_pairs = 0
    for val in freq:
        k = freq[val]
        total_pairs += k * (k - 1) // 2
    return total_pairs
```

> **Time and Space Complexity**
>
> **Time:** O(n) for counting frequencies plus O(k) for computing pairs, where k is the number of distinct values.
> 
> **Space:** O(k) for the frequency dictionary.

> **Interviewers Watch For**
>
> Can you derive the formula `k*(k-1)/2`? This is 'k choose 2' from combinatorics. Candidates who know this avoid the O(n^2) brute force entirely.

> **Common Pitfall**
>
> Using nested loops to check all pairs. This is O(n^2) and times out on large inputs. The frequency approach is O(n).

---

## Common follow-up questions

- What if you needed pairs that sum to a target instead of equal pairs? _(Tests the two-sum hash map approach.)_
- What if the input were a stream and you needed a running pair count? _(Tests incrementally updating the count as each new element arrives.)_
- What if you needed the actual pairs, not just the count? _(Tests that enumerating pairs is inherently O(n^2) in the worst case.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_pair_counter)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.