K-diff Pairs in an Array

Medium
482.

K-diff Pairs in an Array

K-diff Pairs in an Array is a medium coding problem on arrays and hash table, asked in Amazon and Microsoft interviews.

Given an integer array nums and an integer k, return the number of unique k-diff pairs in the array.

A k-diff pair is a pair (nums[i], nums[j]) with i != j and |nums[i] - nums[j]| == k. Two pairs are the same if they consist of the same two values, so (1,3) and (3,1) count once.

Example 1

Input
nums = [3,1,4,1,5], k = 2
Output
2
Explanation
The pairs are (1,3) and (3,5). The duplicate 1 does not create a third pair.

Example 2

Input
nums = [1,2,3,4,5], k = 1
Output
4
Explanation
(1,2), (2,3), (3,4) and (4,5).

Example 3

Input
nums = [1,3,1,5,4], k = 0
Output
1
Explanation
Only the value 1 appears more than once.

Constraints

  • 1 <= nums.length <= 10000
  • -10000000 <= nums[i] <= 10000000
  • 0 <= k <= 10000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

K-diff Pairs in an Array — Solution in Python, Java & C++

K-diff Pairs in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

K-diff Pairs in an Array is a medium coding problem on arrays and hash table, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer array nums and an integer k, return the number of unique k-diff pairs in the array.

A k-diff pair is a pair (nums[i], nums[j]) with i != j and |nums[i] - nums[j]| == k. Two pairs are the same if they consist of the same two values, so (1,3) and (3,1) count once.

Example 1

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: The pairs are (1,3) and (3,5). The duplicate 1 does not create a third pair.

Example 2

Input: nums = [1,2,3,4,5], k = 1
Output: 4
Explanation: (1,2), (2,3), (3,4) and (4,5).

Example 3

Input: nums = [1,3,1,5,4], k = 0
Output: 1
Explanation: Only the value 1 appears more than once.

Constraints

  • 1 <= nums.length <= 10000
  • -10000000 <= nums[i] <= 10000000
  • 0 <= k <= 10000000

Hints for K-diff Pairs in an Array

  1. Hint 1

    "Unique pairs" means you should be counting values, not index pairs.

  2. Hint 2

    Build a frequency map, then iterate over its distinct keys.

  3. Hint 3

    k == 0 is a special case: the pair is a value paired with itself, so it needs a frequency of at least 2.

How to solve K-diff Pairs in an Array

Because pairs are identified by their values, collapse the array to a frequency map first. Then each distinct value x contributes at most one pair — the one with x + k.

Approach

  1. Count occurrences of every value into a map.
  2. For each distinct key x: if k == 0, add 1 when count[x] > 1.
  3. If k > 0, add 1 when x + k is also a key.
  4. Return the running total.

Why it works

Fixing the smaller element of the pair as x and looking only upward to x + k visits every unordered value pair exactly once, which is precisely the uniqueness rule the problem states.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Checking both x + k and x - k double-counts every pair.
  • Forgetting k == 0 makes duplicate values report a pair for every occurrence.
  • Sorting plus two pointers also works but must skip equal values explicitly.

Reference solution

Python

from typing import List

def findPairs(nums: List[int], k: int) -> int:
    if k < 0:
        return 0
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    total = 0
    for x in count:
        if k == 0:
            if count[x] > 1:
                total += 1
        elif x + k in count:
            total += 1
    return total

Java

public static int findPairs(int[] nums, int k) {
    if (k < 0) return 0;
    HashMap<Integer, Integer> count = new HashMap<>();
    for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
    int total = 0;
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        if (k == 0) {
            if (e.getValue() > 1) total++;
        } else if (count.containsKey(e.getKey() + k)) {
            total++;
        }
    }
    return total;
}

C++

int findPairs(vector<int>& nums, int k) {
    if (k < 0) return 0;
    unordered_map<int, int> count;
    for (int x : nums) count[x]++;
    int total = 0;
    for (auto& e : count) {
        if (k == 0) {
            if (e.second > 1) total++;
        } else if (count.find(e.first + k) != count.end()) {
            total++;
        }
    }
    return total;
}

JavaScript

var findPairs = function(nums, k) {
    if (k < 0) return 0;
    const count = {};
    for (let i = 0; i < nums.length; i++) {
        const key = String(nums[i]);
        count[key] = (count[key] || 0) + 1;
    }
    let total = 0;
    const keys = Object.keys(count);
    for (let i = 0; i < keys.length; i++) {
        const x = Number(keys[i]);
        if (k === 0) {
            if (count[keys[i]] > 1) total++;
        } else if (count[String(x + k)] !== undefined) {
            total++;
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets