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 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.

Description Solution Video 22:57

532. K-diff Pairs in an Array

Medium46.3% acceptance8 companies

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 <= 10⁴
-10⁷ <= nums[i] <= 10⁷
0 <= k <= 10⁷

Asked at 8 companies

Infosys Salesforce Expedia

TCS

Google Amazon Bloomberg Microsoft

Topics

22:57

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

532. K-diff Pairs in an Array

Asked at 8 companies

Topics

Similar problems