#532

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

K-diff Pairs in an Array

Solve K-diff Pairs in an Array by counting unique differences with a hash map or sorted two-pointer sweep.

array hash table two pointers binary search sorting

Problem Statement

You are given an integer array nums and a nonnegative integer k. Your task is to return how many distinct value pairs have absolute difference exactly k. The pair is defined by values, so repeated positions do not create extra answers once the same value pair has already been counted.

For example, nums = [3,1,4,1,5] with k = 2 produces 2 because the unique pairs are (1,3) and (3,5). When k = 0, you are looking for duplicated values such as (1,1), which means frequency handling matters more than raw scanning.

Examples

Example 1

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

Output: 2

There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2

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

Output: 4

There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3

Input: nums = [1,3,1,5,4], k = 0

Output: 1

There is one 0-diff pair in the array, (1, 1).

Constraints

1 <= nums.length <= 104
-107 <= nums[i] <= 107
0 <= k <= 107

Solution Approach

Use frequency counting as the default path

Build a hash map from value to count. If k is negative, the answer is immediately 0 because an absolute difference cannot be negative. If k = 0, count how many values appear at least twice. If k > 0, iterate through the unique keys and add one whenever key + k is also present. This directly enforces uniqueness because each starting value contributes at most one pair.

Use sorting plus two pointers when asked to avoid extra hash lookups

Sort nums, then run two pointers i and j with j always ahead of i. Compare nums[j] - nums[i] to k. If the difference is too small, move j; if too large, move i; if equal, record one pair and skip every duplicate on both sides before continuing. This version is interview-friendly when the discussion naturally moves toward two pointers, but duplicate skipping is the part that usually breaks correctness.

Choose logic based on the k = 0 split

This problem has a sharp branch that changes what a valid pair means. For k > 0, you want two different values with a gap of k. For k = 0, you want one value appearing multiple times. Treating both cases with the same naive set logic often undercounts or overcounts, so make that branch explicit early in your explanation and code.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

With a hash map, time is O(n) on average and space is O(n) because you count frequencies and then scan unique values. With sorting plus two pointers, time is O(n log n) from the sort and space is O(1) extra if the sort is in place, but that route needs stricter duplicate handling after each match.

What Interviewers Usually Probe

They mention unique pairs, which signals that duplicate values must be collapsed instead of counted by index.
They highlight k = 0, which is a cue to switch from difference lookup to frequency-at-least-two logic.
They ask about Array, Hash Table, and Two Pointers together, which usually means they want you to compare the hash-count method with the sorted duplicate-safe sweep.

Common Pitfalls or Variants

Common pitfalls

Counting index pairs instead of unique value pairs, especially when the array contains repeated numbers.
Using the same rule for k = 0 and k > 0, which misses that zero-diff pairs require duplicates of the same value.
Forgetting to skip duplicates in the sorted two-pointer approach, causing the same pair to be counted multiple times.

Follow-up variants

Return the actual unique k-diff pairs instead of just the count, which means storing the value pairs you confirm.
Handle many queries with different k values on the same nums array, which changes whether preprocessing frequencies or sorting is more useful.
Count pairs with difference at most k instead of exactly k, which turns the sorted two-pointer logic into a window-style counting problem.

FAQ

What is the best approach for K-diff Pairs in an Array?

The most direct approach is frequency counting with a hash map. For k > 0, count each unique value x where x + k exists. For k = 0, count values whose frequency is at least 2. That matches the problem's uniqueness rule with minimal edge-case friction.

Why does k = 0 need separate handling?

Because a zero-diff pair is really a duplicated value pair like (1,1). Looking only for x + k when k = 0 is not enough unless you also verify that the value appears more than once.

Can I solve this with sorting and two pointers?

Yes. After sorting, move two pointers based on the current difference and skip duplicates after every match. The approach is valid, but most mistakes happen when repeated values are not skipped correctly.

Why not count every pair of indices with absolute difference k?

The problem asks for unique value pairs, not all index combinations. If nums contains repeated values, multiple index choices may represent the same pair and should only be counted once.

How does the array scanning plus hash lookup pattern fit this problem?

You scan the array once to build frequencies, then scan the unique values to test whether the matching value for a k-gap exists. That pattern works well here because membership checks are cheap and uniqueness is handled at the value level rather than the index level.

terminal

Solution

Solution 1: Hash Table

Since $k$ is a fixed value, we can use a hash table $\textit{ans}$ to record the smaller value of the pairs, which allows us to determine the larger value. Finally, we return the size of $\textit{ans}$ as the answer.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        ans = set()
        vis = set()
        for x in nums:
            if x - k in vis:
                ans.add(x - k)
            if x + k in vis:
                ans.add(x)
            vis.add(x)
        return len(ans)

Continue Practicing

#350 intersection of two arrays ii #349 intersection of two arrays #1346 check if n and its double exist