Domain 2MediumCORE

K-diff Pairs in an Array

We are given an integer array nums and a target difference k. We need to return the number of unique pairs (a, b) such that both elements exist in the array at different indices (i != j) and their absolute difference is exactly k.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Two Pointers

532. K-diff Pairs in an Array

Model: qwen3.5:9b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 35.5%


Problem Breakdown

We are given an integer array nums and a target difference k. We need to return the number of unique pairs (a, b) such that both elements exist in the array at different indices (i != j) and their absolute difference is exactly k.

Key constraints:

  1. Unique Pairs: The pair {3, 5} is identical to {5, 3}. We count unique value combinations, not index permutations.
  2. Index Constraint: Even if values are the same (e.g., [1, 1]), they must be at different indices (i != j). This implies for k=0, we need duplicates in the array to form a valid pair.
  3. Values: Integers can be negative or large (±107\pm 10^7).

Intuition

A brute-force solution would use nested loops checking every index combination (i,j)(i, j) where i≠ji \neq j. This is O(N2)O(N^2). Given the constraint nums.length <= 10^4, an N2N^2 approach might hit Time Limit Exceeded (TLE).

We need to optimize lookups. Since we care about values and their existence, a Hash Map (Frequency Counter) allows us to check if a number exists in O(1)O(1) time on average.

The core insight is that for any value num present in the array:

  • If k > 0: We only need to look forward or backward once per unique number to avoid double counting pairs (e.g., checking if num + k exists covers both (num, num+k) and (num+k, num)).
  • If k == 0: The pair is (x, x). This requires the value x to appear at least twice in the array.

Approach

  1. Frequency Map: Create a hash map (Counter) storing every number in nums and its frequency count.
  2. Iterate Unique Elements: Iterate through the unique keys of this map. Iterating over values is safer than indices to handle duplicates naturally, but we must iterate only once per distinct value found.
  3. Check Conditions:
    • If k > 0: Check if num + k exists in our frequency map. If it does, increment the result counter. We do not check num - k because that would double count pairs (e.g., checking for both (1,3) and (3,5) when iterating keys).
    • If k == 0: Check if the current number’s frequency is greater than or equal to 2 (count[num] >= 2). This ensures we have two distinct indices with that value.
  4. Return: Return the accumulated count.

Complexity Analysis

  • Time Complexity: O(N)O(N). Building the Counter takes one pass (O(N)O(N)). Iterating through unique keys takes at most NN iterations (worst case all elements are unique), and map lookups are O(1)O(1). Total is linear.
  • Space Complexity: O(N)O(N). We store every element in a hash map for the frequency count.

Solution

from collections import Counter
from typing import List

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        # Build frequency map to handle duplicates and O(1) lookups
        freq = Counter(nums)
        
        count = 0
        
        # Iterate over unique numbers only. 
        # We use .keys() because we want to process each distinct value once.
        for num in freq.keys():
            if k > 0:
                # If k is positive, check if the target (num + k) exists.
                # Checking both directions would double count pairs like {1,3} and {3,1}.
                if (num + k) in freq:
                    count += 1
            else:
                # Special case for k = 0. 
                # We need at least two occurrences of the same number to form a pair with different indices.
                if freq[num] >= 2:
                    count += 1
                    
        return count

Edge Cases Handled

  • k=0: The code explicitly checks freq[num] >= 2. If [1,3,1,5,4] and k=0, only the number 1 has frequency ≥2\ge 2, so it counts as one pair. Single occurrences are ignored for k=0k=0.
  • Negative Numbers: Python’s hash map handles negative integers correctly without special logic adjustments.
  • Empty Array / No Pairs: The loop simply won’t find matches, returning 0, which is correct behavior (though constraints say length ≥1\ge 1).
  • Duplicates in Input: Handled by the frequency counter; we iterate unique keys to ensure pair uniqueness based on values.