Pairs With Constant Difference — Problem Statement & Solution Guide

HashingMediumMixed

TimeO(n)

SpaceO(n)

Problem Description

You are provided with an array nums consisting of distinct integers. Your task is to identify all unique pairs of elements (a, b) such that the absolute difference between them is exactly equal to a given constant k. Specifically, you must find pairs where |a - b| == k.

Return a list of these pairs. The order of the pairs in the returned list does not matter, nor does the order of elements within each pair. However, each pair should be unique; for instance, if (x, y) is a valid pair, (y, x) should not be included again.

Although a brute-force approach checking all possible pairs yields a time complexity of O(n^2), you are expected to implement a solution that efficiently locates these pairs. Note that while the problem statement mentions O(n^2) as a baseline, optimal solutions typically utilize hashing to achieve O(n) average time complexity, which is preferred for large inputs.

DSA Pattern Breakdown

"Pairs With Constant Difference"

medium

WHY DOES IT MATTER?

Constant‑difference pair problems appear in many domains—frequency analysis, cryptographic key matching, and recommendation engines—where you need to detect relationships defined by a fixed offset. Mastering the hash‑set pattern teaches you how to replace nested loops with constant‑time lookups, a skill that dramatically improves scalability.

OPTIMIZATION CHALLENGE

The key insight is to treat the problem as a membership test: for each element a, the only candidates that can form a valid pair are a + k and a - k. By pre‑loading all elements into a hash‑set, we can answer these membership queries in O(1) time, collapsing the double loop into a single pass.

REAL-WORLD CONNECTION

Imagine a distributed cache that stores timestamps of events. To detect events that occurred exactly k seconds apart, you query the cache for each timestamp's partner (t + k). This mirrors the hash‑set solution, turning a potentially O(n²) scan of logs into O(n) cache lookups.

During an interview, write the hash‑set solution first, then discuss edge cases (k = 0, negative k, empty array) and how you would adapt the code for duplicates or "at most k" variations. This shows depth and flexibility.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem of finding pairs with a constant absolute difference is a classic example of leveraging constant‑time lookups to avoid quadratic enumeration. A naive double loop checks every possible pair, leading to O(n²) time, which quickly becomes infeasible for large n (e.g., n > 10⁵). The optimal paradigm uses a hash‑set (or hash‑map) to store each element as we iterate, allowing us to query in O(1) whether the complement (value ± k) exists. Because the array contains distinct integers, each valid pair is discovered exactly once, and we can collect them without worrying about duplicates. An alternative optimal strategy is to sort the array and apply a two‑pointer sweep, which also guarantees O(n log n) time due to sorting but uses O(1) extra space. Both approaches illustrate the broader algorithmic principle of transforming a pair‑search problem into a membership‑check problem, thereby collapsing the combinatorial explosion.

Interview Questions on This Problem

Q1How would you modify the solution if the array could contain duplicate numbers and you needed to return each unique pair only once?

First, count frequencies using a hash‑map. For each distinct value x, check if x + k exists. If k == 0, ensure the frequency of x is at least 2 before emitting (x, x). Otherwise, emit (x, x + k) once regardless of how many times each appears. This keeps the overall complexity O(n) while handling duplicates correctly.

Q2Can you solve the problem in O(n) time without extra space beyond the output list? Explain the trade‑offs.

Yes, by sorting the array in‑place (O(n log n) time, O(1) extra space) and then using two pointers to find pairs with difference k. The trade‑off is that we lose the strict O(n) linear guarantee, but we gain constant auxiliary space, which may be required in memory‑constrained environments.

Q3What would change if the requirement was to find pairs where the difference is at most k instead of exactly k?

With the "at most k" condition, after sorting we can use a sliding window: expand the right pointer while nums[right] - nums[left] <= k, and for each left, all elements between left+1 and right form valid pairs. This yields O(n log n) time due to sorting and O(1) extra space, or O(n) time with a balanced BST to maintain a dynamic window if we need to avoid sorting.

Examples

Example 1

Input

nums = [1, 5, 3, 7, 9], k = 2

Output

[[1, 3], [5, 7], [7, 9]]

Explanation: We check for pairs with a difference of 2. - For 1: 1+2=3 exists in the array. Pair: [1, 3]. - For 5: 5+2=7 exists in the array. Pair: [5, 7]. - For 3: 3+2=5 exists, but [3, 5] is the same as [5, 3] which is covered by the 5 check (or we just check one direction to avoid duplicates). Let's stick to checking if `num + k` exists. - For 7: 7+2=9 exists in the array. Pair: [7, 9]. - For 9: 9+2=11 does not exist. Result: [[1, 3], [5, 7], [7, 9]].

Example 2

Input

nums = [10, 20, 30, 40], k = 10

Output

[[10, 20], [20, 30], [30, 40]]

Explanation: We look for pairs with a difference of 10. - 10 + 10 = 20 (exists). Pair: [10, 20]. - 20 + 10 = 30 (exists). Pair: [20, 30]. - 30 + 10 = 40 (exists). Pair: [30, 40]. - 40 + 10 = 50 (does not exist). Result: [[10, 20], [20, 30], [30, 40]].

Example 3

Input

nums = [1, 2, 3, 4, 5], k = 0

Output

[]

Explanation: The problem states that the array contains distinct elements. Therefore, no two elements are equal. Since k=0 implies we are looking for pairs where `a == b`, and all elements are distinct, there are no such pairs. Result: []

Example 4

Input

nums = [100, 102, 104, 106], k = 4

Output

[[100, 104], [102, 106]]

Explanation: We look for pairs with a difference of 4. - 100 + 4 = 104 (exists). Pair: [100, 104]. - 102 + 4 = 106 (exists). Pair: [102, 106]. - 104 + 4 = 108 (does not exist). - 106 + 4 = 110 (does not exist). Result: [[100, 104], [102, 106]].

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= k <= 10^9
All elements in nums are distinct.

Optimal Approach & Strategy

Insert all numbers into a hash set, then for each number x check if x + k (or x - k) is present; add the pair when found.

Brute Force Approach

Loop over every i and j (i < j) and check if |nums[i] - nums[j]| == k, collecting matching pairs.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[][]}
 */
var findPairs = function(nums, k) {
    const seen = new Set();
    const result = [];
    for (const num of nums) {
        if (seen.has(num - k)) {
            result.push([num - k, num]);
        }
        if (seen.has(num + k)) {
            result.push([num, num + k]);
        }
        seen.add(num);
    }
    return result;
};

class Solution {
public:
    vector<vector<int>> findPairs(vector<int>& nums, int k) {
        unordered_set<int> seen;
        vector<vector<int>> result;
        for (int num : nums) {
            if (seen.count(num - k)) {
                result.push_back({num - k, num});
            }
            if (seen.count(num + k)) {
                result.push_back({num, num + k});
            }
            seen.insert(num);
        }
        return result;
    }
};

class Solution {
    public List<List<Integer>> findPairs(int[] nums, int k) {
        Set<Integer> seen = new HashSet<>();
        List<List<Integer>> result = new ArrayList<>();
        for (int num : nums) {
            if (seen.contains(num - k)) {
                result.add(Arrays.asList(num - k, num));
            }
            if (seen.contains(num + k)) {
                result.add(Arrays.asList(num, num + k));
            }
            seen.add(num);
        }
        return result;
    }
}

class Solution:
    def findPairs(self, nums: List[int], k: int) -> List[List[int]]:
        seen = set()
        result = []
        for num in nums:
            if num - k in seen:
                result.append([num - k, num])
            if num + k in seen:
                result.append([num, num + k])
            seen.add(num)
        return result

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[][]}
 */
var findPairs = function(nums, k) {
    const seen = new Set();
    const result = [];
    for (const num of nums) {
        if (seen.has(num - k)) {
            result.push([num - k, num]);
        }
        if (seen.has(num + k)) {
            result.push([num, num + k]);
        }
        seen.add(num);
    }
    return result;
};

Asked in Top Tech Interviews

uncategorizedmediumnone

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Pairs With Constant Difference Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Hashing

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Pairs With Constant Difference — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor