Count position pairs whose values differ by exactly k

Interview craft Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
from collections import Counter
vals, k = [1, 5, 3, 3, 7], 2
seen: Counter[int] = Counter()
total = 0
for v in vals:
    total += seen[v - k] + seen[v + k]
    seen[v] += 1
print(total)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 5

Right: 1-3 twice, 5-3 twice and 5-7.

Looking only backwards in the counter is what turns the O(n²) double loop into one pass without double counting.

Why not the others?
  • B 3. Both 3s pair with 1 and with 5.
  • C 10. Only earlier values are counted, so each pair counts once.

30-second answer

The brute force checks all pairs in O(n²). Instead, walk the list once with a counter of values seen so far: each value v pairs with every earlier v - k and v + k. Add both counts, then record v. O(n) time and O(n) memory: the counter replaces the inner loop.

Practise saying it · 30 s. No recording, just a timer

Explain counting pairs with a counter.

Say your answer out loud, then check which of these points you covered:

  • Counter of earlier values
  • Add v - k and v + k
  • O(n)

Deep dive

This is the 'lookup inside a loop becomes a hash map' improvement.

Because k ≥ 1, v - k and v + k are different values, so nothing is counted twice.

Counting earlier values only is what keeps each pair counted once.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
from collections import Counter


def pairs_k_apart(vals: list[int], k: int) -> int:
    earlier: Counter[int] = Counter()  # values seen before this one
    total = 0
    for v in vals:
        total += earlier[v - k] + earlier[v + k]
        earlier[v] += 1
    return total

Common mistakes

  • Counting both directions over the whole list, which doubles the answer.
  • Using a set instead of a counter, which loses repeated values.

Senior take & follow-ups

Point to the inner loop in the brute force and say what replaces it.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if k can be 0?

    Show hint

    Then count pairs of equal values: for each value with c copies, add c(c - 1) / 2.

  2. What if you need distinct value pairs instead of position pairs?

    Show hint

    Use a set of values and check v + k for each.

Suggest a fix if something here is wrong or out of date.