☕ DSA Java Articles

Topics › Linked List › Medium Problems of DLL

Find Pairs with Given Sum in Doubly Linked List

Medium TUF ID 452 A2Z

Java source ↗ Edit this article ↗

Problem

You are given the head of a doubly linked list whose values are sorted in ascending order and distinct, and an integer target. Return every pair of values (a, b) with a < b and a + b == target. Each node may be used in at most one pair, and since values are distinct a node can never be paired with itself. List the pairs with the smaller value first, ordered by the smaller value.

Constraints: 0 ≤ n ≤ 10^5, values and target fit in a 32-bit signed integer.

Example 1

head = 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9, target = 7
answer = (1, 6), (2, 5)       // 3 is absent, so 4 has no partner

Example 2

head = 1 <-> 5 <-> 9, target = 10
answer = (1, 9)               // 5 + 5 = 10, but there is only one 5 and it cannot pair with itself

Example 3

head = 1 <-> 2 <-> 3, target = 10
answer = (none)

This is Two Sum on a doubly linked list. The doubly linked part matters: the prev pointer lets us walk backwards from the tail, which is exactly what the two-pointer technique on a sorted array needs.

Approach 1: Brute force

Intuition. Enumerate every pair of nodes. Fixing the first node with an outer loop and scanning the nodes after it with an inner loop ensures each unordered pair is examined once and no node is paired with itself. Because the list is sorted, pairs are discovered in increasing order of their first element, which is the required output order with no extra sorting.

Algorithm.

  1. For each node a from the head onward:
  2. For each node b after a:
  3. If a.val + b.val == target, record (a.val, b.val).
  4. Return the recorded pairs.
static List<int[]> bruteForce(Node head, int target) {
    List<int[]> pairs = new ArrayList<>();
    for (Node a = head; a != null; a = a.next) {
        for (Node b = a.next; b != null; b = b.next) {
            if ((long) a.val + b.val == target) pairs.add(new int[]{a.val, b.val});
        }
    }
    return pairs;
}

Complexity. Time O(n^2): n(n-1)/2 pairs, constant work each. Space O(1) beyond the output.

The sum is computed in long. Two values near 2 × 10^9 overflow int when added, and a wrapped-around sum could accidentally equal the target. The test file includes 1000000000 + 2000000000 with target = -1294967296, which is exactly what int addition wraps to; the correct answer is no pair.

For n = 10^5 this is 5 × 10^9 comparisons, far too many. Note that the brute force does not use the sorted property at all, so it is leaving information on the table.

Approach 2: Better, hash set of seen values

Intuition. While walking the list, at node t ask: “have I already seen target - t.val?” A hash set of the values seen so far answers that in constant time. Each pair is found exactly once, when its larger element is reached, because the smaller one was inserted earlier. This approach ignores the sort order, so it also works for an unsorted list; the price is O(n) extra memory.

Because pairs are discovered at their larger element, they come out in increasing order of the larger value, which for a sorted list is decreasing order of the smaller value. A final sort on the first element restores the required order.

Algorithm.

  1. Create an empty set seen and an empty result list.
  2. For each node t: compute need = target - t.val as a long.
    • If need is within the int range and is in seen, record the pair (min, max) of need and t.val.
    • Insert t.val into seen.
  3. Sort the pairs by their first element and return them.
static List<int[]> better(Node head, int target) {
    List<int[]> pairs = new ArrayList<>();
    Set<Integer> seen = new HashSet<>();
    for (Node t = head; t != null; t = t.next) {
        long need = (long) target - t.val;                    // long: target - value can overflow int
        if (need >= Integer.MIN_VALUE && need <= Integer.MAX_VALUE && seen.contains((int) need)) {
            int other = (int) need;
            pairs.add(new int[]{Math.min(other, t.val), Math.max(other, t.val)});
        }
        seen.add(t.val);
    }
    pairs.sort((x, y) -> Integer.compare(x[0], y[0]));      // the sweep discovers pairs by their larger element; order them by the smaller one
    return pairs;
}

Complexity. Time O(n) for the sweep plus O(p log p) to sort the p ≤ n/2 pairs found. Space O(n) for the set.

The insert-after-check order is what prevents self-pairing. When t.val * 2 == target, the complement equals t.val, but it is not yet in seen at the time of the check, and since values are distinct no later node will supply it either.

Approach 3: Optimal, two pointers from both ends

Intuition. On a sorted sequence, put one pointer at the smallest value and one at the largest. If their sum is too small, the only way to increase it is to move the left pointer right; if too big, move the right pointer left. If it equals the target, record the pair and move both pointers inward, since each node participates in at most one pair (with distinct values, a given left has at most one partner). Every step retires one node for good, so the sweep is linear.

On an array this needs index arithmetic. On a doubly linked list the prev pointer gives us the leftward step for free, which is the whole reason the problem is posed on a DLL.

Algorithm.

  1. If the list is empty return no pairs.
  2. Set left = head and walk right to the tail.
  3. While left != right and right.next != left (the pointers have neither met nor crossed):
    • sum = left.val + right.val (in long).
    • If sum == target, record (left.val, right.val), then left = left.next and right = right.prev.
    • Else if sum < target, left = left.next.
    • Else right = right.prev.
  4. Return the pairs.
static List<int[]> optimal(Node head, int target) {
    List<int[]> pairs = new ArrayList<>();
    if (head == null) return pairs;
    Node left = head, right = head;
    while (right.next != null) right = right.next;            // find the tail
    while (left != right && right.next != left) {             // stop when the pointers meet or cross
        long sum = (long) left.val + right.val;
        if (sum == target) {
            pairs.add(new int[]{left.val, right.val});
            left = left.next;
            right = right.prev;
        } else if (sum < target) {
            left = left.next;                                 // too small: the only way up is a bigger left value
        } else {
            right = right.prev;                               // too big: the only way down is a smaller right value
        }
    }
    return pairs;
}

Dry run on 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9, target = 7:

left right sum action
1 9 10 too big, right = 8
1 8 9 too big, right = 6
1 6 7 record (1, 6); left = 2, right = 5
2 5 7 record (2, 5); left = 4, right = 4
4 4   left == right, stop

Complexity. Time O(n): finding the tail is one pass, and the sweep moves each pointer at most n times in total. Space O(1) beyond the output.

Why the two stopping conditions? left == right catches the case where the pointers land on the same node, which happens when an odd number of nodes remains between them. right.next == left catches the case where they pass each other, which happens when both pointers move after a match on two adjacent nodes: left becomes the old right and right becomes the old left. Checking only left != right would loop forever in that second case.

Why is it correct to skip values? Suppose left.val + right.val < target. For the current left, every candidate partner to the left of right is even smaller, so left has no partner at all among the remaining nodes and can be retired. The symmetric argument applies when the sum is too large. On a match, left has found its only possible partner (values are distinct, so no other node has value target - left.val), and likewise for right, so both can move.

Edge cases and pitfalls