How do you solve K-diff Pairs in an Array?

Build a frequency map of all numbers. If k == 0, count how many numbers appear more than once. Otherwise, for each unique number, check if number + k exists in the map and increment the pair count accordingly. This yields an O(n) time and space solution.

K-diff Pairs in an Array

Q: What is the time complexity of K-diff Pairs in an Array?

O(n). Building the frequency map takes O(n). Iterating over the keys and checking for complements is O(n) on average due to O(1) hash map lookups.

Q: What pattern does K-diff Pairs in an Array use?

The Pattern: Hash Maps (Frequency Counting and Complement Lookup) The Heuristic: When counting pairs with a fixed difference, transform the problem into a frequency map and check for complements in O(1) time, enabling a single pass solution that avoids costly nested loops.

Medium Hash Maps

Problem

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 defined as an integer pair (nums[i], nums[j]) where i != j and |nums[i] - nums[j]| == k.

1 ≤ nums.length ≤ 10⁴
−10⁷ ≤ nums[i] ≤ 10⁷
0 ≤ k ≤ 10⁷

Example

Input: nums = [3, 1, 4, 1, 5], k = 2

Output: 2

The unique pairs with difference 2 are (1, 3) and (3, 5). The algorithm first counts the frequency of each number: {1: 2, 3: 1, 4: 1, 5: 1}. Since k is 2, it checks for each number if number + 2 exists. For 1, 3 exists; for 3, 5 exists; for 4, 6 does not exist; for 5, 7 does not exist. Thus, two pairs are counted. If k were 0, the algorithm would count numbers with frequency greater than 1.

Approach

Straightforward Solution

A brute-force approach would check every pair of numbers, resulting in O(n^2) time complexity, which is inefficient for large inputs.

Core Observation

The problem reduces to counting unique pairs where the difference between elements is exactly k. This can be reframed as checking for each number if its complement (number + k) exists, or if k is zero, counting duplicates.

Path to Optimal

Preview

Recognizing that the problem is about existence and frequency of numbers, a hash map (dictionary) can store counts of each number. For k > 0, iterating over keys and checking if key + k exists allows counting pairs in O(n) time…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build a frequency map of all numbers. If k == 0, count how many numbers appear more than once…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Building the frequency map takes O(n). Iterating over the keys and checking for complements is O(n) on average due to O(1) hash map lookups.

Space

O(n)

The frequency map stores counts for up to n unique numbers, requiring O(n) auxiliary space.

Pattern Spotlight

Hash Maps (Frequency Counting and Complement Lookup)

When counting pairs with a fixed difference, transform the problem into a frequency map and check for complements in O(1) time, enabling a single pass solution that avoids costly nested loops.

Solution

Python

1class Solution:
  def findPairs(self, nums: list[int], k: int) -> int:
      counts = {}
4
      for num in nums:
          counts[num] = counts.get(num, 0) + 1
7
      pairs = 0
9
      for num in counts:
          if k == 0:
              if counts[num] > 1:
                  pairs += 1
          else:
              if num + k in counts:
                  pairs += 1
17
      return pairs

Step-by-Step Solution

Build Frequency Map of Numbers

3counts = {}
5for num in nums:
6    counts[num] = counts.get(num, 0) + 1

Objective

To count the occurrences of each number in the input array for efficient lookup.

Key Insight

By storing the frequency of each number in a hash map, the algorithm can quickly determine if a complement exists or if duplicates are present. This transforms the problem from pairwise comparison to simple membership and frequency checks, enabling O(n) time complexity.

Interview Quick-Check

Core Logic

The frequency map enables O(1) average-time lookups to check for complements or duplicates.

Common Pitfalls & Bugs

Forgetting to increment counts correctly or initializing counts improperly can lead to incorrect pair counts.

Count Unique k-diff Pairs Using Frequency Map

To iterate over unique numbers and count valid pairs based on the value of k.

Return the Total Count of Unique k-diff Pairs

To output the final count of unique pairs found.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 6 Critical

counts[num] = counts.get(num, 0) + 1

Increment the count for the current number in the frequency map.

Accurately tracking the frequency of each number is critical to distinguish duplicates (for k=0) and to verify the existence of complements (for k>0).

Line 15 Critical

if num + k in counts:

Check if the complement (num + k) exists in the frequency map.

This membership check identifies valid pairs efficiently, leveraging the hash map's O(1) average lookup time.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does the algorithm treat the case k = 0 differently from k > 0?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct K-diff Pairs in an Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the K-diff Pairs in an Array drill

or drill a free problem

1	`class Solution:`
2	`def findPairs(self, nums: list[int], k: int) -> int:`
3	`counts = {}`
4
5	`for num in nums:`
6	`counts[num] = counts.get(num, 0) + 1`
7
8	`pairs = 0`
9
10	`for num in counts:`
11	`if k == 0:`
12	`if counts[num] > 1:`
13	`pairs += 1`
14	`else:`
15	`if num + k in counts:`
16	`pairs += 1`
17
18	`return pairs`