Find all pairs on integer array whose sum is equal to given number

The problem, simply

You get an array of whole numbers and a target number. Find every pair of positions i < j where arr[i] + arr[j] equals the target.

The same value can sit at two positions, and each position counts on its own. In [1, 5, 7, -1, 5] with target 6, the 1 pairs with both 5s, so (1, 5) shows up twice. Give back the pairs (or how many there are).

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every pair of positions and keep the ones that add up to the target.

1. For each i, for each j > i, check arr[i] + arr[j] == target.
2. If yes, add the pair.

class Solution {
    public List<int[]> findPairs(int[] arr, int target) {
        List<int[]> pairs = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] + arr[j] == target) {
                    pairs.add(new int[] { arr[i], arr[j] });
                }
            }
        }
        return pairs;
    }
}

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

Way 2: the clever way

Walk left to right with a board that counts how many times each number has appeared so far (a hash map).

1. For the number x in front of you, the partner you need is need = target - x.
2. Look up need on the board. If it was seen c times, that is c new pairs.
3. Then add x to the board. Doing it after the lookup stops a number from pairing with itself.

class Solution {
    public List<int[]> findPairs(int[] arr, int target) {
        List<int[]> pairs = new ArrayList<>();
        Map<Integer, Integer> seen = new HashMap<>();   // number -> how many times so far
        for (int x : arr) {
            int need = target - x;
            int c = seen.getOrDefault(need, 0);
            for (int k = 0; k < c; k++) {
                pairs.add(new int[] { need, x });         // one pair per earlier partner
            }
            seen.merge(x, 1, Integer::sum);               // now write x on the board
        }
        return pairs;
    }

    // If only the number of pairs is wanted, this is O(n) no matter how many pairs exist.
    public long countPairs(int[] arr, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        long count = 0;
        for (int x : arr) {
            count += seen.getOrDefault(target - x, 0);
            seen.merge(x, 1, Integer::sum);
        }
        return count;
    }
}

How long it takes: one walk with a quick board lookup per number, plus writing out the p pairs, so O(n + p). Counting alone is O(n). Extra room: the board holds up to n numbers, O(n).

Watch out for

• Use counts, not a plain set, when duplicates matter. A set would find only one pair in [1, 1, 1, 1] with target 2.
• target - x can overflow for values near the int limits. Use long if the input can be that large.
• Ask the interviewer: do they want every pair of positions, or only different value pairs? (1, 5) twice versus once changes the code.

What interviewers ask next

• Only distinct value pairs? Sort, then use two pointers from both ends. When the sum matches, record it and skip all copies of both values. O(n log n) time, O(1) extra room.
• Return the indices of one pair (LeetCode Two Sum)? Store index instead of count, and return as soon as need is found.
• Pairs with difference k? Look up x - k and x + k instead of target - x.
• The array is too big for memory? Sort it on disk, then stream it from both ends with two pointers.
• Three numbers that add up to a target? Fix one number, then run this pair search on the rest. O(n^2).

Remember this

Grown-up words: the whiteboard is a hash map from value to count, the partner is the complement target - x, and this is the classic Two Sum pattern.