Show problems as
Classic problem #532MediumArrayHash TableTwo PointersBinary SearchSorting

K-diff Pairs in an Array

Real-world version: Reading Pairs at a Fixed Gap
Tracked in this browser only
Read K-diff Pairs in an Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_pairs(nums: list[int], k: int) -> int:
Java
public int findPairs(int[] nums, int k)

More on the same topics