Pairs With a Fixed Gap

Medium

You are given an integer array values and a number gap. Count the distinct pairs of values (a, b) with a ≤ b and b - a = gap, where a and b sit at different positions in the array. Pairs are compared by value: if the same pair of numbers can be formed in several ways, it still counts once.

Example 1

values=[5, 1, 5, 9, 3], gap=4 → 2

The pairs (1, 5) and (5, 9) fit. There are two 5s, but (1, 5) is a single pair of values and counts once.

Example 2

values=[2, 2, 2, 7], gap=0 → 1

A difference of 0 needs two equal elements, so there is exactly one pair of values, (2, 2).

Example 3

values=[-1, 4, 9], gap=5 → 2

Constraints

1 ≤ len(values) ≤ 10⁴
-10⁷ ≤ values[i] ≤ 10⁷
0 ≤ gap ≤ 10⁷

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Two Pointers Binary Search Sorting

Similar problems

Spells Without Neighbors Medium Values in Both Lists Easy Shared Values With Repeats Easy Twice as Much Easy Triples Under a Limit Medium

Input

values=[5, 1, 5, 9, 3], gap=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 125 tests on the server, hidden ones included.