0616MediumArrayHash TableTwo PointersBinary SearchSorting

Reading Pairs at a Fixed Gap

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A probe wrote down n temperature readings into nums, in the order it took them. Readings can be negative and the same reading can be written down more than once. You are also given the gap k, which is not negative.

Two different positions i and j form a match when the absolute difference between nums[i] and nums[j] is exactly k. Matches are identified by the pair of values they use and nothing else: two matches that carry the same two values are the same match, and swapping which value comes first does not create a new one.

Return the number of distinct matches. Note that when k is 0 a match uses one value twice, so it needs that value to have been written down at two different positions.

Examples

Example 1

Input: nums = [4, 1, 7, 3], k = 3
Output: 2

The value pairs sitting three apart are (1, 4) and (4, 7), so there are two distinct matches.

Example 2

Input: nums = [6, 2, 8, 2, 6, 6], k = 4
Output: 1

Only the value pair (2, 6) sits four apart. It shows up at several combinations of positions, but they all carry the same two values and count once.

Example 3

Input: nums = [4, 4, 5, 6, 6, 7], k = 0
Output: 2

With a gap of zero, the values 4 and 6 each appear at two positions and give one match apiece, while 5 and 7 appear once and give none.

Constraints

1 <= nums.length <= 10^4
-10^7 <= nums[i] <= 10^7
0 <= k <= 10^7

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_pairs(nums: list[int], k: int) -> int:

Java

public int findPairs(int[] nums, int k)

The intended approach

Time O(n) — one pass to tally and one pass over the distinct values.Space O(u) where u is the number of distinct readings.

Because a match is named by its two values, the first step is a single pass that records how many times each value was written down. A gap of zero puts the same value on both sides of the match, so the count of values recorded at least twice is the answer in that case. For a positive gap the two values are different, so each distinct value is looked up once against the value one gap above it and every match is found from its lower value only, which stops it being counted twice.

Pythonentry point: find_pairs

def find_pairs(nums, k):
    # O(n) time, O(u) space for the u distinct readings. A match is named by a
    # pair of values, so the positions themselves never matter once each value
    # knows how often it appears. With a gap of zero the two values coincide,
    # so a value qualifies exactly when it was logged at least twice; with a
    # positive gap the values differ and each distinct value is checked once
    # against the value that sits one gap above it.
    counts = {}
    for value in nums:
        counts[value] = counts.get(value, 0) + 1
    if k == 0:
        return sum(1 for repeats in counts.values() if repeats >= 2)
    return sum(1 for value in counts if value + k in counts)

The obvious version

Try every ordered pair of different positions. Whenever the two readings sit exactly the gap apart, drop the pair of values, smaller one first, into a set. The size of the set is the answer.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_pairs(nums, k):
    seen = set()
    n = len(nums)
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if abs(nums[i] - nums[j]) == k:
                low = min(nums[i], nums[j])
                high = max(nums[i], nums[j])
                seen.add((low, high))
    return len(seen)

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in