Find the triplet that sum to a given value

The problem, simply

You get an array of numbers and a target. Find three numbers at three different positions that add up to the target. Give back the three numbers, or say there are none.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every group of three positions.

class Solution {
    public int[] findTriplet(int[] arr, int target) {
        int n = arr.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                for (int k = j + 1; k < n; k++)
                    if (arr[i] + arr[j] + arr[k] == target)
                        return new int[] { arr[i], arr[j], arr[k] };
        return new int[0];                      // none found
    }
}

How long it takes: about n^3 / 6 groups, O(n^3). Extra room: O(1).

Way 2: the clever way

Sort, then for each first number solve "find two numbers with a given sum" using two hands.

1. Sort the array.
2. For each i: need = target - arr[i]. Put l = i + 1 and r = n - 1.
3. While l < r: if arr[l] + arr[r] == need, done. If it is less, move l right. If it is more, move r left.

Why moving a hand is safe: if arr[l] + arr[r] is too small, then arr[l] with any partner left of r is even smaller. So arr[l] can never be part of the answer, and we drop it. The same idea works for r when the sum is too big.

class Solution {
    public int[] findTriplet(int[] arr, int target) {
        int[] a = arr.clone();
        Arrays.sort(a);
        int n = a.length;
        for (int i = 0; i < n - 2; i++) {
            int need = target - a[i];          // the other two must make this
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = a[l] + a[r];
                if (sum == need) return new int[] { a[i], a[l], a[r] };
                if (sum < need) l++;           // too small: drop the left one
                else r--;                      // too big: drop the right one
            }
        }
        return new int[0];
    }
}

How long it takes: sorting is O(n log n), and for each of the n first numbers the hands walk at most n steps, so O(n^2) in total. Extra room: O(1) besides the copy and the sort.

Watch out for

• Forgetting to sort. The squeeze only makes sense on a sorted array.
• When asked for all different triplets, skip repeated values: skip i if a[i] == a[i - 1], and after a match move l and r past copies of the values you used.
• Sums can overflow int with huge values. Use long for sum and need if needed.

What interviewers ask next

• Return all unique triplets that sum to 0 (LeetCode 3Sum)? Same loops, keep going after a match, and skip repeated values as above. Still O(n^2).
• Closest sum to the target? Same squeeze, but remember the sum with the smallest distance to the target instead of stopping.
• Without sorting? For each i, use a hash set for the two sum part on the rest of the array. O(n^2) time but O(n) extra room.
• Four numbers? Fix two numbers with two loops and squeeze the other two: O(n^3). In general k numbers take O(n^(k-1)).
• Count triplets with sum less than the target? When a[l] + a[r] < need, every r' between l + 1 and r also works, so add r - l and move l.

Remember this

Grown-up words: the hands are two pointers, the inner part is the two sum problem on a sorted array, and the whole thing is the 3Sum pattern.