Find a pair with a given difference

The problem, simply

You get an unsorted array and a number n. Is there a pair of numbers, at two different positions, whose difference is exactly n? Return true or false.

The difference of a pair does not care about order: 80 and 2 are 78 apart either way. So a negative n means the same as its positive size.

A story to remember it

Picture it

Examples

Way 1: the simple way

Check every pair of positions. If any two numbers are exactly n apart, say yes.

class Solution {
    public boolean findPair(int[] arr, int n) {
        long want = Math.abs((long) n);
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (Math.abs((long) arr[i] - arr[j]) == want) return true;
            }
        }
        return false;
    }
}

How long it takes: every pair once, O(n^2). Extra room: O(1).

Way 2: the clever way

Sort, then use two fingers that both walk right. This is different from the "two numbers that add up to" trick, where the fingers start at opposite ends. Here both start at the left, because we care about the gap between them.

1. Sort the array. Take want = |n|.
2. i = 0, j = 1.
3. If i == j, move j (a number cannot pair with itself).
4. If arr[j] - arr[i] == want, return true.
5. If the gap is too small, move j right to widen it.
6. If the gap is too big, move i right to shrink it.
7. When j falls off the end, return false.

import java.util.*;

class Solution {
    public boolean findPair(int[] arr, int n) {
        long want = Math.abs((long) n);
        Arrays.sort(arr);
        int i = 0, j = 1;
        while (j < arr.length) {
            if (i == j) { j++; continue; }        // never pair a number with itself
            long gap = (long) arr[j] - arr[i];
            if (gap == want) return true;
            if (gap < want) j++;                  // too close, widen
            else i++;                             // too far, shrink
        }
        return false;
    }
}

How long it takes: sorting is O(n log n), then each finger moves at most n times, O(n). Total O(n log n). Extra room: O(1) besides the sort.

Another way: a hash set

Walk the numbers once and remember what you have seen in a hash set, a bag where you can ask "is this number inside?" instantly. For each number x, ask whether x - want or x + want is already in the bag.

import java.util.*;

class Solution {
    public boolean findPair(int[] arr, int n) {
        long want = Math.abs((long) n);
        Set<Long> seen = new HashSet<>();
        for (int x : arr) {
            if (seen.contains(x - want) || seen.contains(x + want)) return true;
            seen.add((long) x);
        }
        return false;
    }
}

This takes O(n) time on average but O(n) extra room. It also handles n = 0 for free: the second 5 finds the first 5 in the bag. Pick it when time matters more than memory, and the sorting way when memory is tight.

Watch out for

• A negative n. Use its size, Math.abs(n), or the fingers chase a gap that can never appear.
• Starting the fingers at opposite ends, like in two sum. Then moving either finger shrinks the gap, so you cannot tell which way to go.
• Overflow: arr[j] - arr[i] with values near two billion does not fit in an int. Do it in long.
• Sorting changes the caller's array. Copy it first if that matters.

What interviewers ask next

• Count all pairs with difference k (LeetCode 532, "K-diff Pairs"). Count each value with a hash map. For k > 0, count values x where x + k exists. For k = 0, count values that appear at least twice.
• Return the pair, not just yes or no. Return arr[i] and arr[j] instead of true.
• What if the array is already sorted? Then Way 2 is O(n) time and O(1) room.
• Another O(n log n) way: after sorting, for each x binary search for x + want in the part to its right.

Remember this

Grown-up words: the two fingers are two pointers moving in the same direction (a sliding window over a sorted array), and the bag of numbers seen is a hash set.