K-diff Pairs in an Array solution and explanation
Infosys
TCS
Google
9 more videos on this problem
K diff Pairs in an Array | Leetcode 532 | ArraysAyushi Sharma · 22:57 · 14K views
(Remade) K-Diff Pairs in Array | Leetcode 532Nideesh Terapalli · 4:06 · 8K views
K-Diff Pairs in an Array | Facebook Coding Interview Question | LeetCode 532EazyAlgo · 12:48 · 4K views
Leetcode - K-diff Pairs in an Array (Python)Timothy H Chang · 4:02 · 4K views
K-diff Pairs in an Array | Leetcode 532 | Live Coding session 🔥🔥🔥| Easy Peasy Maps solutionCoding Decoded · 8:48 · 2K views
(Old) Leetcode 532 - K-diff Pairs in an Array | ArrayNideesh Terapalli · 5:19 · 1K views
K-diff Pairs in an Array leetcode 532 videoEasyLeetcode · 7:14 · 688 views
K-diff Pair in an Array | In-Depth Explanation | LeetCode - 532 SolvedCoder X · 14:07 · 659 views
Daily Leetcode #680: Feb 09, 2022 - 532. K-diff Pairs in an ArrayProgramming Live with Larry · 11:45 · 377 views
K-diff Pairs in an Array | LeetCode 532 | October LeetCode Challenge | Day 3Learn Code Repeat · 15:06 · 324 views
The problem
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.lengthi != 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] <= 1070 <= 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.
from collections import Counter
def findPairs(nums, k):
count = 0
freq = Counter(nums)
for num in freq:
if k == 0:
if freq[num] > 1:
count += 1
else:
if num + k in freq:
count += 1
return countimport java.util.HashMap;
public class Solution {
public int findPairs(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
int count = 0;
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (int key : map.keySet()) {
if (k == 0) {
if (map.get(key) >= 2) count++;
} else if (map.containsKey(key + k)) {
count++;
}
}
return count;
}
}#include <unordered_map>
#include <vector>
int findPairs(std::vector<int>& nums, int k) {
std::unordered_map<int, int> freq_map;
int count = 0;
for (int num : nums) {
freq_map[num]++;
}
for (const auto& pair : freq_map) {
if (k == 0) {
if (pair.second > 1) count++;
} else if (freq_map.find(pair.first + k) != freq_map.end()) {
count++;
}
}
return count;
}function findPairs(nums, k) {
let map = new Map();
let count = 0;
for (let num of nums) {
map.set(num, (map.get(num) || 0) + 1);
}
for (let [key, val] of map) {
if (k == 0) {
if (val > 1) count++;
} else if (map.has(key + k)) {
count++;
}
}
return count;
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int findPairs(int* nums, int numsSize, int k) {
int *hashMap = (int*)calloc(20001, sizeof(int));
int count = 0;
for(int i = 0; i < numsSize; i++) {
hashMap[nums[i] + 10000]++;
}
for(int i = 0; i < 20001; i++) {
if(hashMap[i]) {
int num = i - 10000;
if(k == 0) {
if(hashMap[i] >= 2) count++;
} else if(k > 0 && num + k <= 10000 && hashMap[num + k + 10000]) {
count++;
}
}
}
free(hashMap);
return count;
}using System;
using System.Collections.Generic;
public class Solution {
public int FindPairs(int[] nums, int k) {
Dictionary<int, int> map = new Dictionary<int, int>();
int count = 0;
foreach (var num in nums) {
if (map.ContainsKey(num)) map[num]++;
else map[num] = 1;
}
foreach (var kvp in map) {
if (k == 0) {
if (kvp.Value > 1) count++;
} else {
if (map.ContainsKey(kvp.Key + k)) count++;
}
}
return count;
}
}This Python code uses a Counter to handle frequency counting. It correctly differentiates between the k=0 special case and positive k values, iterating over the elements in the frequency dictionary.
Time Complexity: O(n). Space Complexity: O(n) - frequency dict for unique elements.
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.
def findPairs(nums, k):
nums.sort()
left, right, count = 0, 0, 0
while right < len(nums):
if right == left or nums[right] - nums[left] < k:
right += 1
elif nums[right] - nums[left] > k:
left += 1
else: # nums[right] - nums[left] == k
left += 1
count += 1
while right + 1 < len(nums) and nums[right] == nums[right + 1]:
right += 1
right += 1
return countimport java.util.Arrays;
public class Solution {
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
int count = 0, left = 0, right = 0;
while (right < nums.length) {
if (right == left || nums[right] - nums[left] < k) {
right++;
} else if (nums[right] - nums[left] > k) {
left++;
} else {
left++;
count++;
while (right < nums.length && nums[right] == nums[right - 1]) right++;
}
}
return count;
}
}#include <vector>
#include <algorithm>
int findPairs(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
int count = 0, left = 0, right = 0;
while (right < nums.size()) {
if (right == left || nums[right] - nums[left] < k) {
++right;
} else if (nums[right] - nums[left] > k) {
++left;
} else { // nums[right] - nums[left] == k
++count;
++left;
while (right < nums.size() && nums[right] == nums[right - 1]) {
++right;
}
}
}
return count;
}function findPairs(nums, k) {
nums.sort((a, b) => a - b);
let left = 0, right = 0, count = 0;
while (right < nums.length) {
if (right <= left || nums[right] - nums[left] < k) {
right++;
} else if (nums[right] - nums[left] > k) {
left++;
} else {
count++;
left++;
while (right < nums.length - 1 && nums[right] == nums[right + 1]) right++;
right++;
}
}
return count;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int findPairs(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), compare);
int left = 0, right = 1, count = 0;
while (right < numsSize) {
int diff = nums[right] - nums[left];
if (diff < k || left == right) {
right++;
} else if (diff > k) {
left++;
} else { // diff == k
count++;
left++;
while (right < numsSize - 1 && nums[right] == nums[right + 1])
right++;
right++;
}
while (left < numsSize - 1 && nums[left] == nums[left - 1])
left++;
}
return count;
}using System;
public class Solution {
public int FindPairs(int[] nums, int k) {
Array.Sort(nums);
int count = 0, left = 0, right = 0;
while (right < nums.Length) {
if (right == left || nums[right] - nums[left] < k) {
right++;
} else if (nums[right] - nums[left] > k) {
left++;
} else {
count++;
left++;
while (right < nums.Length - 1 && nums[right] == nums[right + 1]) right++;
right++;
}
}
return count;
}
}In this Python solution, the array is sorted, then two slowly advancing pointers attempt to find unique pairs. The strategy handles tight comparisons, updating the left if necessary to avoid counting duplicates.
Time Complexity: O(n log n). Space Complexity: O(1) while operating in-place.
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.
function findPairs(nums: number[], k: number): number {
const ans = new Set<number>();
const vis = new Set<number>();
for (const x of nums) {
if (vis.has(x - k)) {
ans.add(x - k);
}
if (vis.has(x + k)) {
ans.add(x);
}
vis.add(x);
}
return ans.size;
}func findPairs(nums []int, k int) int {
ans := make(map[int]struct{})
vis := make(map[int]struct{})
for _, x := range nums {
if _, ok := vis[x-k]; ok {
ans[x-k] = struct{}{}
}
if _, ok := vis[x+k]; ok {
ans[x] = struct{}{}
}
vis[x] = struct{}{}
}
return len(ans)
}use std::collections::HashSet;
impl Solution {
pub fn find_pairs(nums: Vec<i32>, k: i32) -> i32 {
let mut ans = HashSet::new();
let mut vis = HashSet::new();
for &x in &nums {
if vis.contains(&(x - k)) {
ans.insert(x - k);
}
if vis.contains(&(x + k)) {
ans.insert(x);
}
vis.insert(x);
}
ans.len() as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| HashMap Method | Time Complexity: O(n). Space Complexity: O(n) - frequency dict for unique elements. |
| Sorting and Two Pointers | Time Complexity: O(n log n). Space Complexity: O(1) while operating in-place. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Method | O(n) | O(n) | General case for unsorted arrays; fastest approach using constant-time hash lookups |
| Sorting + Two Pointers | O(n log n) | O(1) extra | When memory usage should be minimal or the array is already sorted |
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.