Find pairs with a given sum in a DLL

The problem, simply

You get a doubly linked list: every box has an arrow to the next box and an arrow back to the box before it. The numbers are sorted from small to big, and no number repeats. You also get a target.

Find every pair of boxes whose numbers add up to target. Give back the pairs, smaller number first, in increasing order of the first number.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every pair.

1. Put finger a on each box in turn.
2. For each a, walk finger b over every box after it.
3. If a.data + b.data == target, write the pair down. Since the list is sorted, you can stop the inner walk as soon as the sum gets too big.

class Solution {
    public static List<List<Integer>> findPairsWithGivenSum(int target, Node head) {
        List<List<Integer>> out = new ArrayList<>();
        for (Node a = head; a != null; a = a.next) {
            for (Node b = a.next; b != null; b = b.next) {
                int sum = a.data + b.data;
                if (sum == target) out.add(Arrays.asList(a.data, b.data));
                if (sum >= target) break;           // sorted, so later b only get bigger
            }
        }
        return out;
    }
}

How long it takes: about n * n / 2 pairs in the worst case, O(n^2). Extra room: two fingers, O(1), not counting the answer.

Way 2: the clever way

Use the seesaw trick with two pointers. The back arrows are what make it possible: right can walk from the tail toward the head.

1. Put left on the head. Walk to the end once to put right on the tail.
2. While left is before right: add the two numbers.
3. Equal to the target? Save the pair, move left forward and right back.
4. Too big? Move right back. Too small? Move left forward.
5. Stop when the fingers meet or cross.

14

class Solution {
    public static List<List<Integer>> findPairsWithGivenSum(int target, Node head) {
        List<List<Integer>> out = new ArrayList<>();
        if (head == null) return out;
        Node left = head, right = head;
        while (right.next != null) right = right.next;      // walk to the tail once
        while (left != right && right.next != left) {       // stop when they meet or cross
            int sum = left.data + right.data;
            if (sum == target) {
                out.add(Arrays.asList(left.data, right.data));
                left = left.next;
                right = right.prev;
            } else if (sum > target) {
                right = right.prev;                         // too heavy, lighter partner
            } else {
                left = left.next;                           // too light, heavier partner
            }
        }
        return out;
    }
}

How long it takes: one walk to the tail, then every step moves at least one finger inward, O(n). Extra room: two fingers, O(1).

Watch out for

• Forgetting to find the tail first. right must start at the last box, not at null.
• Using the trick on an unsorted list. It only works because sorted order tells you which finger to move.
• Duplicates. If values can repeat, a match like (2, 5) with two 2s and three 5s is really 6 pairs. Count the runs of equal values on both sides and multiply.
• A singly linked list. There is no back arrow, so either copy into an array or use a hash set of seen values in one pass.

What interviewers ask next

• Do it on a singly linked list. One pass with a hash set: for each value, check if target - value is in the set, then add the value. O(n) time and O(n) space.
• Count triplets that add up to x. Fix the first box, then run this same two pointer squeeze on the boxes after it. That is O(n^2).
• Find the pair whose sum is closest to target. Same squeeze, but keep the best |sum - target| seen so far instead of only exact matches.
• What if the list is a binary search tree instead? Walk it in order from the small end and the big end at the same time with two stacks, the same seesaw idea.

Remember this

Grown-up words: the kids lined up by weight are a sorted doubly linked list, the back arrows are prev pointers, the two hands are the two pointer technique, and sending kids away is shrinking the search window.