How to Solve K-diff Pairs in an Array

For K-diff Pairs in an Array, the key is counting unique value pairs, not index combinations. The cleanest solution uses frequency counting: when k > 0, check whether x + k exists; when k = 0, count values that appear at least twice. A sorted two-pointer version also works, but only if you skip duplicates carefully after finding each valid pair.

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

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.

How GhostInterview Helps

• It identifies the k = 0 branch early so the solver does not force one buggy rule across both cases.
• It steers the solution toward unique-value counting, preventing duplicate-heavy arrays from inflating the result.
• It compares the hash lookup path against the sorted two-pointer path for this exact problem, including where duplicate skipping fails.

Topic Pages

• Array
• Hash Table
• Two Pointers
• Binary Search
• Sorting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.