Find a Pair with the Given Difference

Title: Find a Pair with the Given Difference

Given an array of integers and a target difference, how do you quickly find two elements whose difference equals that target? This is a classic array problem that shows up often in coding interviews, and it is a great exercise in trading a brute-force nested loop for a faster, sorted-array approach.

In this guide, you will learn how to solve the Find a Pair with the Given Difference problem using sorting and two pointers. We will walk through the algorithm, write a complete Java program, trace it on a sample input, and cover the edge cases and follow-up questions an interviewer is likely to raise.

Understanding the Problem

You are given an array of integers arr and a non-negative integer diff. You need to determine whether there exists a pair of elements arr[i] and arr[j] such that arr[i] - arr[j] == diff (or equivalently arr[j] - arr[i] == diff, since the pair can be reported in either order).

For example, given arr = {5, 20, 3, 2, 50, 80} and diff = 78, the pair (80, 2) works because 80 - 2 = 78. The brute-force way is to check every pair with two nested loops, which costs O(n^2) time. Sorting the array first lets you find the pair in O(n log n) time using two pointers.

Approach / Algorithm Steps

1. If diff is negative, convert it to its absolute value, since a difference pair is symmetric.
2. Sort the array in ascending order so related elements become comparable with two pointers.
3. Initialize two pointers, left = 0 and right = 0, both starting at the beginning of the sorted array.
4. Loop while both pointers stay within bounds: compute arr[right] - arr[left].
5. If the computed difference equals diff and left != right, a pair is found; return it.
6. If the computed difference is less than diff, advance right to increase the gap.
7. Otherwise, advance left to shrink the gap.
8. If the pointers exhaust the array without a match, no such pair exists.

Java Program

import java.util.Arrays;

public class FindPairWithGivenDifference {

    public static int[] findPairWithDifference(int[] arr, int diff) {
        if (arr == null || arr.length < 2) {
            return null;
        }

        int target = Math.abs(diff);
        int[] sorted = arr.clone();
        Arrays.sort(sorted);

        int left = 0;
        int right = 0;
        int n = sorted.length;

        while (right < n) {
            if (left != right) {
                int currentDiff = sorted[right] - sorted[left];
                if (currentDiff == target) {
                    return new int[] {sorted[left], sorted[right]};
                } else if (currentDiff < target) {
                    right++;
                } else {
                    left++;
                }
            } else {
                right++;
            }
        }

        return null;
    }

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

        int[] result = findPairWithDifference(arr, diff);

        if (result != null) {
            System.out.println("Pair found: " + result[0] + ", " + result[1]);
        } else {
            System.out.println("No pair found with difference " + diff);
        }
    }
}

Explanation of the Program

• findPairWithDifference first guards against a null array or an array with fewer than two elements, since no pair can exist in that case.
• The target difference is normalized with Math.abs(diff) so the method behaves the same whether the caller passes a positive or negative difference.
• The original array is cloned before sorting with Arrays.sort(sorted) so the caller’s input array is left untouched.
• left and right both start at index 0. When they coincide, right is advanced because comparing an element with itself is meaningless.
• Inside the loop, currentDiff is the gap between the two pointed-at elements. If it matches target, the pair is returned immediately.
• If currentDiff is too small, moving right forward increases the gap; if it is too large, moving left forward shrinks the gap. Because the array is sorted, this always moves toward the target instead of away from it.
• If right reaches the end of the array without a match, the method returns null, signaling that no such pair exists.

Step-by-Step Trace

Trace the algorithm on arr = {90, 70, 20, 80, 50} with diff = 45. After sorting, the array becomes {20, 50, 70, 80, 90}. No pair in this array actually has a gap of 45, so the trace shows how the pointers walk the whole array and correctly report that no pair exists.

At each step, the invariant holds: sorted[right] - sorted[left] is the smallest unexplored gap at or above the previous gap, so once the pointers cross the target the search terminates correctly, either with a match or by exhausting right.

Examples

Example 1: A Pair Exists

int[] arr = {5, 20, 3, 2, 50, 80};
int diff = 78;
// Output: Pair found: 2, 80

Example 2: No Matching Pair

int[] arr = {90, 70, 20, 80, 50};
int diff = 45;
// Output: No pair found with difference 45

Example 3: Negative Difference Input

int[] arr = {1, 8, 3, 15, 10};
int diff = -5;
// Output: Pair found: 3, 8

Common Mistakes to Avoid

These mistakes come up specifically when solving this problem under interview conditions.

• Forgetting to take the absolute value of diff – passing a negative diff without normalizing it makes the comparison currentDiff == target never true. Always compute Math.abs(diff) before the main loop.
• Sorting the caller’s original array – calling Arrays.sort(arr) directly mutates the input, surprising callers who expected the original order preserved. Clone the array first with arr.clone().
• Not skipping the case where left equals right – without the left != right check, the algorithm can report a ‘pair’ made of the same element compared with itself when diff == 0. Explicitly advance right whenever the pointers coincide.
• Using nested loops on large inputs – the brute-force O(n^2) approach works but times out on large arrays. Sorting plus two pointers brings it down to O(n log n).
• Confusing this with the two-sum problem – the difference problem moves pointers based on whether the gap is too small or too large, which is the opposite direction logic from a sum-based two-pointer search. Mixing the two leads to an infinite loop or a missed match.

Additional Considerations

The sorting step dominates the overall cost. Arrays.sort on primitive int[] uses a dual-pivot quicksort, which runs in O(n log n) time on average. The two-pointer scan that follows runs in O(n), since left and right only ever move forward and together traverse the array once. The overall time complexity is therefore O(n log n), with O(n) extra space for the cloned, sorted array.

If you cannot use extra space, you can sort the array in place instead of cloning it, but that destroys the caller’s original ordering, so only do this when the method is explicitly allowed to mutate its input. A hash-set approach can also solve this problem in O(n) time and O(n) space by checking, for each element x, whether x + diff is already in the set.

Edge Cases to Test

Make sure your implementation handles these boundary scenarios.

• Empty array or array with a single element
• diff equal to zero
• Negative diff value
• Array containing duplicate elements
• Array containing negative numbers
• No pair exists for the given difference
• Multiple pairs satisfy the same difference
• Integer.MIN_VALUE or Integer.MAX_VALUE present, risking overflow in subtraction

Interview Follow-up Questions

Once you have the base solution working, expect an interviewer to push further with questions like these.

• What if the array is already sorted? – skip the sort step entirely and run the two-pointer scan directly, dropping the complexity to O(n).
• What if you need to find all pairs with the given difference, not just one? – keep scanning instead of returning early, advancing both pointers past a match and collecting every valid pair into a list.
• What if you cannot use Arrays.sort because the input must remain read-only and extra memory is limited? – fall back to a hash-set lookup of size O(n), or accept the O(n^2) brute-force if memory is truly bounded to O(1).
• What if the array is a stream of numbers arriving one at a time? – maintain a running hash set of seen values, and for each new value x check whether x – diff or x + diff has already been seen.
• What if the array is too large to fit in memory? – sort it externally using an external merge sort, then stream through it with the same two-pointer logic reading from disk in chunks.

Conclusion

Finding a pair with a given difference is a compact problem that rewards recognizing the right pattern: sort first, then let two pointers close in on the target gap instead of comparing every pair. The same two-pointer idea generalizes to many other array problems, so it is worth internalizing beyond this one exercise.

Try adapting the code to return every matching pair, or to use a hash set when the array must stay unsorted. You can learn more about array problems like this one in the Arrays category on this site.