Count triplet with sum smaller than a given value

The problem, simply

You get an array of n different numbers and a limit sum. Pick three numbers from three different positions. Count how many such groups of three add up to less than sum.

You only count the groups. You do not need to list them.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every group of three positions i < j < k and count the ones whose sum is under the limit.

class Solution {
    public long countTriplets(int[] arr, int sum) {
        int n = arr.length;
        long count = 0;
        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] < sum) count++;
        return count;
    }
}

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

Way 2: the clever way

Sort the numbers. Fix the smallest member of the group, then find the other two with two fingers that walk toward each other.

1. Sort the array.
2. For each i, set l = i + 1 and r = n - 1.
3. If arr[i] + arr[l] + arr[r] < sum, then arr[r] can be swapped for anything between l and r, because those are all smaller. That is r - l groups. Add them all and move l right.
4. Otherwise arr[r] is too big with arr[l], and with any bigger l too. Move r left.
5. Stop when the fingers meet, then move i.

import java.util.*;

class Solution {
    public long countTriplets(int[] arr, int sum) {
        int n = arr.length;
        Arrays.sort(arr);
        long count = 0;
        for (int i = 0; i < n - 2; i++) {
            int l = i + 1, r = n - 1;
            while (l < r) {
                if (arr[i] + arr[l] + arr[r] < sum) {
                    count += r - l;   // arr[r] can be swapped for anything between l and r
                    l++;
                } else {
                    r--;              // arr[r] is too big here
                }
            }
        }
        return count;
    }
}

How long it takes: sorting is O(n log n). For each i the two fingers together take at most n steps, so the loops are O(n^2). Extra room: O(1) besides the sort.

Watch out for

• Forgetting to sort. The "everything between is smaller" idea only holds on a sorted array.
• Moving r after a hit. A hit means l is used up with every partner, so move l.
• Big numbers: three values near two billion overflow an int sum. Cast to long when the values can be large.
• The answer itself can be about n^3 / 6. Return a long.

What interviewers ask next

• Can you print the groups instead? Yes, but there can be O(n^3) of them, so listing them costs that much no matter what.
• Count groups with sum greater than sum? Same fingers: when the group is too big, add r - l and move r left.
• Count groups with sum between low and high? Count those under high + 1 and subtract those under low.
• What about pairs with sum under k? Same idea with two fingers and no fixed i, O(n log n).
• Why not use a hash map like in 3-sum? A hash map answers "is this exact number here", not "how many are smaller". Sorting does the counting for free.

Remember this

Grown-up words: the two fingers are the two pointer technique, and counting the whole stretch at once works because the array is sorted, so all values between the pointers are smaller.