Skip to main content
Talentd

K-diff Pairs in an Array - Solution & Explanation

MediumArrayHash TableTwo PointersBinary Search16 min readAsked at: Amazon, Microsoft, Salesforce +5
Practice this problem

Problem Statement

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

A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:

  • 0 <= i, j < nums.length
  • i != j
  • |nums[i] - nums[j]| == k

Notice that |val| denotes the absolute value of val.

 

Example 1:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: 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
Explanation: 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
Explanation: There is one 0-diff pair in the array, (1, 1).

 

Constraints:

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

Approach Overview

Problem Overview: You are given an integer array nums and an integer k. The task is to count the number of unique pairs (i, j) where the absolute difference between the numbers is exactly k. Duplicate values in the array can exist, but each pair should be counted only once.

Approach 1: HashMap Method (O(n) time, O(n) space)

This approach uses a frequency map built with a hash table. First iterate through the array and store the frequency of every number. Then iterate over the keys and check whether num + k exists in the map. If it does, you found a valid pair. The edge case occurs when k == 0; in that situation you only count numbers whose frequency is greater than 1 because the pair must consist of two equal values.

The key insight is constant-time lookup using hashing. Instead of checking every pair, you reduce the problem to checking whether the complementary value exists. Each lookup takes O(1) average time, so scanning all numbers gives overall O(n) time. This approach works well for unsorted arrays and is typically the most straightforward solution in interviews.

Approach 2: Sorting and Two Pointers (O(n log n) time, O(1) extra space)

This approach first sorts the array using a sorting algorithm, which costs O(n log n). After sorting, use the two pointers technique. Initialize two indices left and right. Move right forward to increase the difference and move left forward to decrease it. When nums[right] - nums[left] == k, record the pair and skip duplicates to ensure uniqueness.

The sorted order allows you to compare differences efficiently without a hash map. Because the pointers only move forward, the scan after sorting runs in O(n). This method is useful when memory usage must remain minimal or when the array is already sorted.

Recommended for interviews: The HashMap method is usually the expected optimal solution because it achieves O(n) time and handles duplicates cleanly with frequency counts. The sorting + two pointers approach is also common and demonstrates strong understanding of array scanning techniques. Mentioning both shows awareness of tradeoffs between time complexity and extra space.

Approach 1: HashMap Method

This approach uses a HashMap to track the frequency of each element in the array. For each unique element, we will check if there's another element that can form a k-diff pair with it. When k is zero, we need to check if there are duplicates present in the list.

The code uses a frequency map stored as an array from -10000 to 10000 to count occurrences of each number. For a k-difference, if k is zero, we count pairs from duplicates. Otherwise, we look for the presence of the number plus k.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) because we iterate over the array and then over the hashmap that is bounded by a constant size. Space Complexity: O(n) to store the frequency map.

Try this approach in the editor →

Approach 2: Sorting and Two Pointers

This approach involves sorting the array initially, then using two pointers to determine unique k-diff pairs. The array being sorted helps us efficiently reduce potential pair checks, and ensure pairs are considered only once.

After sorting, two pointers start from the beginning. We adjust pointers depending on the difference relative to k. Duplicates are handled by skipping same values.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if disregard input.

Try this approach in the editor →

Approach 3: Hash Table

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

We traverse the array nums. For the current number x, we use a hash table vis to record all the numbers that have been traversed. If x-k is in vis, we add x-k to ans. If x+k is in vis, we add x to ans. Then, we add x to vis. Continue traversing the array nums until the end.

Finally, we return the size of ans as the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
HashMap Method

Time Complexity: O(n) because we iterate over the array and then over the hashmap that is bounded by a constant size. Space Complexity: O(n) to store the frequency map.

Sorting and Two Pointers

Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if disregard input.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap MethodO(n)O(n)General case for unsorted arrays; fastest approach using constant-time hash lookups
Sorting + Two PointersO(n log n)O(1) extraWhen memory usage should be minimal or the array is already sorted

Video Solution

K diff Pairs in an Array | Leetcode 532 | Arrays • Ayushi Sharma • 14,827 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is K-diff Pairs in an Array easy or hard?
K-diff Pairs in an Array is classified as a medium difficulty problem. The challenge comes from handling duplicates correctly and counting only unique pairs while keeping the algorithm efficient.
How to solve K-diff Pairs in an Array in O(n)?
Use a hash table to store the frequency of each number. For every unique value, check if value + k exists in the map. When k equals 0, only count numbers with frequency greater than one. This reduces pair checking to constant-time lookups and keeps the total complexity O(n).
K-diff Pairs in an Array Python or Java solution
In Python, the solution typically uses a dictionary or collections.Counter to track frequencies and check num + k. In Java, a HashMap<Integer, Integer> is used for the same logic. Both implementations achieve O(n) time complexity with O(n) extra space.
What is the best approach for K-diff Pairs in an Array?
The HashMap approach is usually the best solution. It stores frequencies of numbers and checks whether num + k exists using constant-time hash lookups. This results in O(n) time complexity and O(n) space complexity, which is optimal for unsorted arrays.
Is K-diff Pairs in an Array asked at Google/Amazon/Meta?
K-diff Pairs in an Array is a common medium-level interview question related to arrays and hash tables. Variants of this pattern appear in interviews at companies like Amazon, Google, and Meta because it tests hash maps, two pointers, and duplicate handling.
What data structure is used in K-diff Pairs in an Array?
The most common data structure used is a hash table (HashMap or dictionary) to store element frequencies and perform O(1) lookups. An alternative approach uses sorting and the two pointers technique to scan the array efficiently without extra memory.
What is the time complexity of K-diff Pairs in an Array?
The optimal HashMap solution runs in O(n) time because each element is processed once and hash lookups take O(1) on average. The sorting + two pointers approach runs in O(n log n) due to the sorting step, followed by a linear scan.

Ready to solve this problem?

Practice K-diff Pairs in an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Number of Bad Pairs

Next

Count Number of Pairs With Absolute Difference K