Find All Pairs with the Given Difference

Title: Find All Pairs with the Given Difference

Understanding the Problem

Given an array of integers and a target difference k, the goal is to find every pair of elements (a, b) from the array such that a - b = k. This is a classic array and hashing problem that shows up often in interviews because it tests whether you reach for a nested loop or recognize the O(n) hashing trick right away.

For example, with the array [5, 20, 3, 2, 50, 80] and k = 78, the only valid pair is (80, 2), because 80 - 2 = 78. In this guide, you’ll build a Java solution using a HashSet, walk through a full dry run, and look at the edge cases an interviewer expects you to mention.

Approach

The brute-force approach checks every pair with two nested loops in O(n^2) time. A faster approach uses a HashSet to look up the matching element in constant time. Here’s the plan:

1. Handle the trivial cases first: if the array is null or has fewer than two elements, return an empty result.
2. Normalize the difference by taking diff = Math.abs(k), since a pair’s difference should not depend on the sign of k.
3. Insert every element of the array into a HashSet<Integer> called seen, so membership checks run in O(1).
4. Iterate over the array a second time. For each element num, compute bigger = num + diff.
5. If bigger exists in seen and num has not already been used to form a pair, record (bigger, num) as a valid pair.
6. Mark num as used in a second HashSet so the same pair is never reported twice.
7. Return the list of pairs once the loop finishes.

Java Program

Here’s a complete, compilable Java program that implements the approach above and prints the pairs it finds.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class FindPairsWithDifference {

    public static List<int[]> findPairs(int[] arr, int k) {
        List<int[]> result = new ArrayList<>();
        if (arr == null || arr.length < 2) {
            return result;
        }

        int diff = Math.abs(k);
        HashSet<Integer> seen = new HashSet<>();
        for (int num : arr) {
            seen.add(num);
        }

        HashSet<Integer> used = new HashSet<>();
        for (int num : arr) {
            int bigger = num + diff;
            if (seen.contains(bigger) && !used.contains(num)) {
                result.add(new int[] {bigger, num});
                used.add(num);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] numbers = {5, 20, 3, 2, 50, 80};
        int k = 78;

        List<int[]> pairs = findPairs(numbers, k);

        if (pairs.isEmpty()) {
            System.out.println("No pairs found with difference " + k);
        } else {
            System.out.println("Pairs with difference " + k + ":");
            for (int[] pair : pairs) {
                System.out.println(pair[0] + " - " + pair[1] + " = " + k);
            }
        }
    }
}

Explanation of the Program

Let’s walk through what each part of findPairs does.

• seen stores every array value once, so checking whether bigger exists in the array is an O(1) operation instead of an O(n) linear scan.
• diff = Math.abs(k) means the method works correctly whether the caller passes k = 78 or k = -78; both describe the same pair relationship.
• The second HashSet, used, prevents the same smaller element from generating the same pair twice when the loop revisits it.
• result stores each pair as a two-element int[], with the larger value at index 0 and the smaller value at index 1.
• The main method prints a friendly message when pairs is empty, instead of silently producing no output.

Step-by-Step Trace

Trace findPairs on the array [1, 5, 9, 2, 12, 7] with k = 5, so diff = 5. The target output is the two pairs (7, 2) and (12, 7).

At the end of each iteration, result holds every pair discovered so far, and used guarantees that each smaller element contributes at most one pair.

Examples

Example 1: Multiple Pairs in One Array

With numbers = {4, 1, 8, 7, 5, 9} and k = 3, the method finds three separate pairs because several elements in the array are exactly 3 apart.

int[] numbers = {4, 1, 8, 7, 5, 9};
int k = 3;
List<int[]> pairs = findPairs(numbers, k);
// Output:
// 7 - 4 = 3
// 4 - 1 = 3
// 8 - 5 = 3

Three pairs come out of a single pass: (7, 4), (4, 1), and (8, 5), each satisfying a - b = 3.

Example 2: No Pairs Exist

Not every array and difference produce a result. With numbers = {10, 20, 30} and k = 5, no two elements are exactly 5 apart.

int[] numbers = {10, 20, 30};
int k = 5;
List<int[]> pairs = findPairs(numbers, k);
// Output:
// No pairs found with difference 5

pairs comes back empty, and the main method’s empty check prints a clear message instead of nothing at all.

Example 3: Negative Difference

Callers do not always pass a positive k. With numbers = {15, 5, 20, 10} and k = -10, the Math.abs(k) normalization makes the method behave exactly as it would for k = 10.

int[] numbers = {15, 5, 20, 10};
int k = -10;
List<int[]> pairs = findPairs(numbers, k);
// Output:
// 15 - 5 = -10
// 20 - 10 = -10

Both pairs, (15, 5) and (20, 10), are found correctly because the method normalizes the sign before searching.

Common Mistakes to Avoid

These are the mistakes that most often turn this problem from a five-minute hashing exercise into a buggy interview answer.

• Treating k as always positive – passing a negative difference like k = -5 without normalizing it causes the lookup to search in the wrong direction and can silently return zero pairs. Normalize with diff = Math.abs(k) before searching.
• Skipping the used-set check – without a second HashSet to mark elements that already formed a pair, the same pair can be reported more than once when both candidate values satisfy the lookup from different iterations. Track used elements separately from seen.
• Assuming the array has no duplicates – a plain HashSet collapses repeated values, so an array like {3, 3, 8} with k = 5 reports only one pair even if the problem expects two. Switch to a frequency HashMap<Integer, Integer> when duplicates must be counted separately.
• Forgetting the k = 0 case – when the difference is zero, every element trivially satisfies num + 0 existing in seen because the set always contains num itself. Add a special check that looks for values appearing at least twice instead of just present once.
• Ignoring integer overflow – computing num + diff when both are close to Integer.MAX_VALUE can overflow and wrap to a negative number, causing a valid pair to be missed. Widen the computation to long when the input range is not guaranteed to be small.

Edge Cases to Test

Walk through these inputs out loud before an interviewer has to ask; it is one of the fastest ways to look senior.

• Empty array
• Single-element array
• k = 0
• Negative k value
• Array with duplicate elements
• No pairs exist for the given difference
• Integer overflow when num + diff exceeds Integer.MAX_VALUE

Additional Considerations

The hashing approach runs in O(n) time: one pass to build seen and one pass to check each element, both linear in the size of the array.

Space usage is O(n) as well, since seen and used can each hold up to n elements in the worst case.

An alternative is to sort the array first and use two pointers, which trades the O(n) extra space for O(n log n) time; that trade-off matters when memory is constrained but time is not.

The overflow edge case matters because Java’s int silently wraps on overflow instead of throwing an exception, so num + diff can produce a small or negative number that happens to collide with an unrelated value in seen, producing an incorrect pair instead of a crash.

Interview Follow-up Questions

Once the base solution is working, expect an interviewer to push on these variations.

• What if the array is already sorted? – use a two-pointer scan instead of hashing to solve it in O(n) time with O(1) extra space.
• What if you need pairs of indices within a window, not just values? – pair a HashMap<Integer, Integer> of value to index with a check that the index gap stays within the allowed window.
• What if the array has duplicates and you need the count of pairs, not just the distinct pairs? – use a frequency HashMap<Integer, Integer> and multiply the counts of the two matching values together.
• What if the input is a massive stream that does not fit in memory? – maintain only a bounded hash window of recently seen values, or process the stream in sorted external chunks and merge.
• What if you must solve it with O(1) extra space? – sort the array in place and use the two-pointer technique, since it needs no auxiliary hash structure.

Conclusion

Finding all pairs with a given difference is a great example of trading a small amount of extra memory for a large drop in time complexity: a HashSet turns an O(n^2) nested loop into a single O(n) pass. Once you have the hashing version working, practice the sorted two-pointer version too, since interviewers like to ask for both.

You can learn more Java array problems like this one on the Arrays category page of DailyJavaConcept.