Module 02 · Hash Maps, Sets, and Frequency State

020. Count Equal Pairs

Interview · Download this solution · All solutions and shared helpers

Problem

Count pairs of indices (i,j) satisfying i<j and nums[i]==nums[j]. Return an integer, not the pairs themselves. Each pair of occurrences counts separately, and an empty or singleton list has zero pairs.

Examples

Example 1

equal_pairs([1, 2, 3, 1, 1, 3])
=> 4

Three pairs of ones and one pair of threes.

Example 2

equal_pairs([])
=> 0

No pair has two endpoints.

Example 3

equal_pairs([7, 7, 7, 7])
=> 6

Four occurrences yield 4*3/2 pairs.

Reveal the worked solution and reasoning

Why this mechanism works

When a new occurrence arrives, it forms one new pair with every earlier equal value. Add the earlier frequency before increasing it. Each pair has one later endpoint, so this charges it exactly once and avoids quadratic pair enumeration.

State and boundaries

frequency[x] counts earlier x occurrences. pairs counts valid pairs entirely inside the processed prefix.

Protocol

Initialize empty frequencies and zero pairs.
Read the incoming value's earlier count.
Add that count to pairs.
Increase its frequency.
Return pairs.

Visualization

occurrences of 1: first, second, third
new pairs:          0       1      2
total for 1: 3

Python implementation

def equal_pairs(nums):
    frequency = {}
    pairs = 0
    for value in nums:
        earlier = frequency.get(value, 0)
        pairs += earlier
        frequency[value] = earlier + 1
    return pairs

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

equal_pairs([1, 2, 3, 1, 1, 3])

L2 equal_pairs: frequency = {}
nums=[1, 2, 3, 1, 1, 3]; frequency={}

L3 equal_pairs: pairs = 0
nums=[1, 2, 3, 1, 1, 3]; frequency={}; pairs=0

L4 equal_pairs: for value in nums:
nums=[1, 2, 3, 1, 1, 3]; frequency={}; pairs=0; value=1

L5 equal_pairs: earlier = frequency.get(value, 0)
nums=[1, 2, 3, 1, 1, 3]; frequency={}; pairs=0; value=1; earlier=0

L7 equal_pairs: frequency[value] = earlier + 1
nums=[1, 2, 3, 1, 1, 3]; frequency={1:1}; pairs=0; value=1; earlier=0

L4 equal_pairs: for value in nums:
nums=[1, 2, 3, 1, 1, 3]; frequency={1:1}; pairs=0; value=2; earlier=0

L7 equal_pairs: frequency[value] = earlier + 1
nums=[1, 2, 3, 1, 1, 3]; frequency={1:1, 2:1}; pairs=0; value=2; earlier=0

L4 equal_pairs: for value in nums:
nums=[1, 2, 3, 1, 1, 3]; frequency={1:1, 2:1}; pairs=0; value=3; earlier=0

... 8 intermediate state changes omitted ...

L4 equal_pairs: for value in nums:
nums=[1, 2, 3, 1, 1, 3]; frequency={1:3, 2:1, 3:1}; pairs=3; value=3; earlier=2

L5 equal_pairs: earlier = frequency.get(value, 0)
nums=[1, 2, 3, 1, 1, 3]; frequency={1:3, 2:1, 3:1}; pairs=3; value=3; earlier=1

L6 equal_pairs: pairs += earlier
nums=[1, 2, 3, 1, 1, 3]; frequency={1:3, 2:1, 3:1}; pairs=4; value=3; earlier=1

L7 equal_pairs: frequency[value] = earlier + 1
nums=[1, 2, 3, 1, 1, 3]; frequency={1:3, 2:1, 3:2}; pairs=4; value=3; earlier=1

Result: 4. Three pairs of ones and one pair of threes.

equal_pairs([])

L2 equal_pairs: frequency = {}
nums=[]; frequency={}

L3 equal_pairs: pairs = 0
nums=[]; frequency={}; pairs=0

Result: 0. No pair has two endpoints.

Why the solution is correct

For each new later endpoint j, the earlier equal positions are exactly those counted by frequency. These new pairs are disjoint from pairs already counted and cover all pairs ending at j. Induction over endpoints accounts for every valid pair once.

Time and space

O(n) expected time and O(u) space; Python integers can represent counts exceeding fixed-width ranges.

Common mistakes

Incrementing first counts a value paired with itself. Counting distinct repeated values answers a different question.

Reasoning card

State: frequency[x] counts earlier x occurrences. pairs counts valid pairs entirely inside the processed prefix.

Invariant: frequency[x] is the number of earlier x values.

Decision to rehearse: Each new occurrence pairs with all previous occurrences.

Finish: Return pairs

Transfer exercise

Derive the equivalent final-frequency formula sum(c*(c-1)//2), then explain the streaming version's advantage.