Count triplets in a sorted DLL whose sum is equal to given value X

The problem, simply

You get a sorted doubly linked list with no repeated numbers, and a number x. Count how many groups of three different boxes add up to exactly x. The order inside a group does not matter, so (2, 6, 9) and (9, 2, 6) are the same group.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every group of three.

1. Finger a walks every box.
2. Finger b walks every box after a.
3. Finger c walks every box after b.
4. If the three numbers add up to x, count it.

class Solution {
    static int countTriplets(Node head, int x) {
        int count = 0;
        for (Node a = head; a != null; a = a.next)
            for (Node b = a.next; b != null; b = b.next)
                for (Node c = b.next; c != null; c = c.next)
                    if (a.data + b.data + c.data == x) count++;
        return count;
    }
}

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

Way 2: the clever way

Fix the first box with i. The other two must add up to need = x - i.data, and they must come after i. Find them with the two pointer squeeze from the pairs problem. The back arrows let right walk left from the tail.

1. Walk to the tail once.
2. For each box i: put left on i.next and right on the tail.
3. While left is before right: if left + right == need, count it and move both inward. If the sum is too small, move left forward. If too big, move right back.
4. Move i forward and repeat.

class Solution {
    static int countTriplets(Node head, int x) {
        if (head == null) return 0;
        Node tail = head;
        while (tail.next != null) tail = tail.next;          // walk to the end once
        int count = 0;
        for (Node i = head; i != null && i.next != null; i = i.next) {
            int need = x - i.data;
            Node left = i.next, right = tail;
            while (left != right && right.next != left) {    // stop when they meet or cross
                int sum = left.data + right.data;
                if (sum == need) {
                    count++;
                    left = left.next;
                    right = right.prev;
                } else if (sum < need) {
                    left = left.next;                        // too light
                } else {
                    right = right.prev;                      // too heavy
                }
            }
        }
        return count;
    }
}

How long it takes: for each of the n choices of i, the squeeze takes at most n steps, O(n^2). Extra room: four fingers, O(1).

Watch out for

• Starting left at the head instead of i.next. Then a box can be used twice, or the same group is counted from different i.
• Duplicate values. The classic version promises distinct values. With repeats, after a match you must count runs of equal values on both sides, and skip equal values of i.
• Fewer than three boxes. The loops handle it and return 0, but say it out loud.

What interviewers ask next

• Can you do better than O(n^2)? Not in general. This is the 3SUM problem, and no one knows a much faster way for it.
• Use a hash map instead. Put every value in a map from value to node, then for each pair (a, b) with a before b look up x - a - b and count it only if it comes after b. That is O(n^2) time but O(n) extra room, so the two pointer way is better here.
• Return the groups instead of counting them. Save (i, left, right) when you match.
• Four numbers (4SUM). Fix two boxes with two loops and squeeze the rest, O(n^3).
• The list is not sorted. Sort it first with merge sort for linked lists, O(n log n), then do the same thing.

Remember this

Grown-up words: the line of kids is a sorted doubly linked list, the pick is the fixed first element, the seesaw game is the two pointer technique, and the whole problem is 3SUM.