Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Find pairs with given sum in doubly linked list

MEDIUMProblemSolveExternal Links

Description

You are given a sorted doubly linked list of positive distinct integers and a target sum. Your task is to find all pairs of nodes whose values add up to the target.

Return the pairs in sorted order by their first element. If no valid pair exists, return an empty list.

Because the list is sorted in ascending order and all values are distinct, each valid pair is unique and consists of two different nodes.

Examples

Example 1

Input: head = 1 ↔ 2 ↔ 4 ↔ 5 ↔ 6 ↔ 8 ↔ 9, target = 7

Output: [(1, 6), (2, 5)]

Explanation: There are two pairs whose values sum to 7. The pair (1, 6) works because 1 + 6 = 7, and the pair (2, 5) works because 2 + 5 = 7. No other combination of two distinct nodes in the list produces a sum of 7.

Example 2

Input: head = 1 ↔ 5 ↔ 6, target = 6

Output: [(1, 5)]

Explanation: Only one pair sums to 6: 1 + 5 = 6. The pair (1, 6) sums to 7, not 6, and (5, 6) sums to 11. So only (1, 5) qualifies.

Example 3

Input: head = 2 ↔ 4 ↔ 6, target = 3

Output: []

Explanation: The smallest possible pair sum is 2 + 4 = 6, which already exceeds the target 3. No pair of nodes can sum to 3, so the result is empty.

Constraints

  • 1 ≤ number of nodes ≤ 10^5
  • 1 ≤ node.data ≤ 10^5
  • 1 ≤ target ≤ 10^5
  • The list is sorted in ascending order
  • All node values are positive and distinct

Editorial

Brute Force

Intuition

The most straightforward approach is to check every possible pair of nodes and see if their values sum to the target. Pick the first node, then walk through every subsequent node and compute the sum. If it matches the target, record the pair. Then move to the second node and repeat with all nodes after it, and so on.

Think of it like standing in a line of people, each holding a number card. You pick up the first card, then walk down the line comparing your card with everyone else's to see if you can make the target sum. When done, you put the card back, pick up the second card, and repeat.

This is a classic nested-loop approach. It does not use the fact that the list is sorted — it works even on unsorted data, which hints that we are leaving performance on the table.

Step-by-Step Explanation

Let's trace through with head = 1 ↔ 2 ↔ 4 ↔ 5 ↔ 6 ↔ 8 ↔ 9 and target = 7:

Step 1: Fix the first pointer at node 0 (value 1). Start the second pointer at node 1 (value 2).

Step 2: Check pair (1, 2): sum = 3 < 7. Not a match. Move the second pointer forward.

Step 3: Check pair (1, 4): sum = 5 < 7. Not a match.

Step 4: Check pair (1, 5): sum = 6 < 7. Just one short of the target.

Step 5: Check pair (1, 6): sum = 7 = target. Match found! Record pair (1, 6). Continue scanning for more pairs with the first pointer at 1.

Step 6: Check pair (1, 8): sum = 9 > 7. Too large. The brute force still checks all remaining pairs.

Step 7: Move the first pointer to node 1 (value 2). Start the second pointer at node 2 (value 4). Check pair (2, 4): sum = 6 < 7.

Step 8: Check pair (2, 5): sum = 7 = target. Another match! Record pair (2, 5).

Step 9: Check pair (2, 6): sum = 8 > 7. No match.

Step 10: Move the first pointer to node 2 (value 4). The smallest pair sum is now 4 + 5 = 9 > 7. All remaining pairs exceed the target. Brute force checks them all anyway.

Step 11: Return the collected pairs: [(1, 6), (2, 5)].

Brute Force — Checking All Pairs in the Doubly Linked List — Watch how the nested loops systematically check every pair of nodes. The outer pointer i fixes one element while the inner pointer j scans all subsequent elements.

Algorithm

  1. Initialize an empty result list.
  2. Set a pointer first to the head of the list.
  3. While first is not null:
    • Set a pointer second to first.next.
    • While second is not null:
      • If first.data + second.data == target, add the pair (first.data, second.data) to the result.
      • Move second to second.next.
    • Move first to first.next.
  4. Return the result list.

Code

class Solution {
public:
    vector<pair<int, int>> findPairsWithGivenSum(Node *head, int target) {
        vector<pair<int, int>> result;
        Node *first = head;

        while (first != nullptr) {
            Node *second = first->next;
            while (second != nullptr) {
                if (first->data + second->data == target) {
                    result.push_back({first->data, second->data});
                }
                second = second->next;
            }
            first = first->next;
        }

        return result;
    }
};
class Solution:
    def findPairsWithGivenSum(self, head, target):
        result = []
        first = head

        while first:
            second = first.next
            while second:
                if first.data + second.data == target:
                    result.append((first.data, second.data))
                second = second.next
            first = first.next

        return result
class Solution {
    public ArrayList<ArrayList<Integer>> findPairsWithGivenSum(Node head, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Node first = head;

        while (first != null) {
            Node second = first.next;
            while (second != null) {
                if (first.data + second.data == target) {
                    ArrayList<Integer> pair = new ArrayList<>();
                    pair.add(first.data);
                    pair.add(second.data);
                    result.add(pair);
                }
                second = second.next;
            }
            first = first.next;
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times and the inner loop runs up to n − 1 times for each iteration. The total number of pair comparisons is n × (n − 1) / 2, which is O(n²). For a list of 10^5 elements, this means approximately 5 × 10^9 comparisons — well beyond typical time limits.

Space Complexity: O(1)

Aside from the output list, we use only two pointer variables. The algorithm itself does not allocate any additional memory proportional to the input size.

Why This Approach Is Not Efficient

The brute force checks all O(n²) pairs, which is extremely slow for n = 10^5 (roughly 5 × 10^9 comparisons). This far exceeds the typical time limit of 10^7 to 10^8 operations per second.

The core problem is that for each element, we perform a linear scan of the remaining list to find its complement. We repeat this expensive scan for every single element.

Missed opportunity: The list is sorted, but the brute force ignores this entirely. It would behave the same on an unsorted list. A sorted structure should allow us to find complements much faster.

Key insight: If we could look up whether a particular value exists in O(1) time, we would not need the inner loop at all. A hash set provides exactly this O(1) lookup, reducing the problem to a single traversal.

Better Approach - Hashing

Intuition

Instead of scanning the entire list for each element's partner, we use a hash set to remember which values we have already seen. As we walk through the list from left to right, for each node with value v we compute the complement target − v and ask the hash set: "have I seen this complement before?" If yes, we have found a pair. If no, we store v in the set and move on.

Imagine you are at a party looking for dance partners. Instead of asking everyone in the room each time, you write each person's number on a guest list as you meet them. When a new person arrives, you glance at the guest list for their perfect partner — instant lookup instead of a room-wide search.

This approach replaces the O(n) inner loop with an O(1) hash set lookup, reducing total time to O(n). However, pairs may be discovered in a different order than their sorted order, so a final sorting step is needed.

Step-by-Step Explanation

Let's trace with head = 1 ↔ 2 ↔ 4 ↔ 5 ↔ 6 ↔ 8 ↔ 9 and target = 7:

Step 1: Initialize an empty hash set. We traverse left to right, checking complements.

Step 2: Process value 1. Complement = 7 − 1 = 6. Is 6 in the set? No (empty). Add 1 to the set. Set: {1}.

Step 3: Process value 2. Complement = 7 − 2 = 5. Is 5 in the set? No. Add 2. Set: {1, 2}.

Step 4: Process value 4. Complement = 7 − 4 = 3. Is 3 in the set? No. Add 4. Set: {1, 2, 4}.

Step 5: Process value 5. Complement = 7 − 5 = 2. Is 2 in the set? YES! Found pair (2, 5). Add 5. Set: {1, 2, 4, 5}.

Step 6: Process value 6. Complement = 7 − 6 = 1. Is 1 in the set? YES! Found pair (1, 6). Add 6.

Step 7: Process values 8 and 9. Complements are −1 and −2 — both negative, impossible in a list of positive numbers. No more pairs.

Step 8: Pairs were found as (2, 5) then (1, 6). Sort by first element: [(1, 6), (2, 5)].

Hashing — One-Pass Complement Lookup — Watch how we build the hash set while scanning. For each element, we check if its complement already exists — giving O(1) pair detection.

Algorithm

  1. Initialize an empty hash set and an empty result list.
  2. Traverse the doubly linked list from head to tail:
    • For the current node value v, compute complement = target − v.
    • If complement exists in the hash set, add the pair (complement, v) to the result.
    • Insert v into the hash set.
  3. Sort the result list by the first element of each pair.
  4. Return the result.

Code

class Solution {
public:
    vector<pair<int, int>> findPairsWithGivenSum(Node *head, int target) {
        vector<pair<int, int>> result;
        unordered_set<int> seen;
        Node *curr = head;

        while (curr != nullptr) {
            int complement = target - curr->data;
            if (seen.count(complement)) {
                result.push_back({complement, curr->data});
            }
            seen.insert(curr->data);
            curr = curr->next;
        }

        sort(result.begin(), result.end());
        return result;
    }
};
class Solution:
    def findPairsWithGivenSum(self, head, target):
        result = []
        seen = set()
        curr = head

        while curr:
            complement = target - curr.data
            if complement in seen:
                result.append((complement, curr.data))
            seen.add(curr.data)
            curr = curr.next

        result.sort()
        return result
class Solution {
    public ArrayList<ArrayList<Integer>> findPairsWithGivenSum(Node head, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        HashSet<Integer> seen = new HashSet<>();
        Node curr = head;

        while (curr != null) {
            int complement = target - curr.data;
            if (seen.contains(complement)) {
                ArrayList<Integer> pair = new ArrayList<>();
                pair.add(complement);
                pair.add(curr.data);
                result.add(pair);
            }
            seen.add(curr.data);
            curr = curr.next;
        }

        result.sort((a, b) -> a.get(0) - b.get(0));
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Traversing the list takes O(n). Each hash set lookup and insertion is O(1) on average. Finding all pairs therefore takes O(n). However, the pairs may not be in sorted order (since complements are discovered based on traversal position, not value order), so we must sort the k result pairs. In the worst case k can be O(n), making the sort O(n log n). Overall: O(n) + O(n log n) = O(n log n).

Space Complexity: O(n)

The hash set stores up to n elements, each requiring O(1) space. Total extra space is O(n). This is the main drawback compared to the brute force, which used O(1) extra space.

Why This Approach Is Not Efficient

The hashing approach dramatically improves upon the O(n²) brute force — it finds all pairs in a single O(n) traversal. However, it has two drawbacks:

  1. O(n) extra space: The hash set stores every element, which is wasteful when n is large (up to 10^5). For memory-constrained environments, this overhead matters.

  2. Sorting overhead: Because pairs are discovered in traversal order rather than sorted order, we need an O(n log n) sort at the end. This makes the total time O(n log n) instead of the O(n) that should be achievable.

Why can we do better? The hashing approach, like the brute force, does not exploit the fact that the list is sorted. It would work equally well on an unsorted list. But a sorted doubly linked list is a very special structure — we can traverse it from both ends simultaneously.

Key insight: Place one pointer at the smallest element (head) and another at the largest element (tail). If their sum is too large, move the right pointer backward to try a smaller value. If too small, move the left pointer forward. This "two-pointer" technique finds all pairs in O(n) time with O(1) extra space — the best of both worlds.

Optimal Approach - Two Pointers

Intuition

Picture two people standing at opposite ends of a sorted number line. The person on the left holds the smallest number, the person on the right holds the largest. They call out their numbers and add them.

  • If the sum is too big, the right person steps left (to a smaller number) — because increasing the left number would only make the sum bigger.
  • If the sum is too small, the left person steps right (to a larger number) — because decreasing the right number would only make the sum smaller.
  • If the sum matches the target, both people record the pair and each steps one position inward to search for more pairs.

They keep going until they meet in the middle. At that point, every possible pair has been considered.

A doubly linked list is perfect for this because the prev pointer lets the right end traverse backward efficiently. No extra data structures are needed — just two pointers walking toward each other.

Step-by-Step Explanation

Let's trace with head = 1 ↔ 2 ↔ 4 ↔ 5 ↔ 6 ↔ 8 ↔ 9 and target = 7:

Step 1: Place the left pointer at the head (value 1) and the right pointer at the tail (value 9).

Step 2: Sum = 1 + 9 = 10 > 7. The sum is too large. Move the right pointer backward using the prev link.

Step 3: Right now at value 8. Sum = 1 + 8 = 9 > 7. Still too large. Move right backward again.

Step 4: Right now at value 6. Sum = 1 + 6 = 7 = target. Match! Record pair (1, 6). Move both pointers inward.

Step 5: Left now at value 2, right now at value 5. Sum = 2 + 5 = 7 = target. Another match! Record pair (2, 5). Move both pointers inward.

Step 6: Left and right both point to value 4 (same node). The pointers have converged — a single element cannot pair with itself. Terminate.

Step 7: Return [(1, 6), (2, 5)]. Pairs are automatically in sorted order because the left pointer always moves forward through increasing values.

Two Pointers Converging from Both Ends — Watch how the left and right pointers converge toward the center, using the sorted order to eliminate impossible pairs at each step.

Algorithm

  1. Initialize left to the head of the list.
  2. Initialize right to the tail of the list (traverse to the last node).
  3. While left and right have not met or crossed:
    • Compute sum = left.data + right.data.
    • If sum == target: record the pair (left.data, right.data), move left forward (left = left.next), and move right backward (right = right.prev).
    • If sum < target: move left forward to increase the sum.
    • If sum > target: move right backward to decrease the sum.
  4. Return the result list. Pairs are already in sorted order because the left pointer always advances through increasing values.

Code

class Solution {
public:
    vector<pair<int, int>> findPairsWithGivenSum(Node *head, int target) {
        vector<pair<int, int>> result;

        // Place left at head, right at tail
        Node *left = head;
        Node *right = head;
        while (right->next != nullptr) {
            right = right->next;
        }

        // Converge from both ends
        while (left != right && right->next != left) {
            int sum = left->data + right->data;

            if (sum == target) {
                result.push_back({left->data, right->data});
                left = left->next;
                right = right->prev;
            } else if (sum < target) {
                left = left->next;
            } else {
                right = right->prev;
            }
        }

        return result;
    }
};
class Solution:
    def findPairsWithGivenSum(self, head, target):
        result = []

        # Place left at head, right at tail
        left = head
        right = head
        while right.next:
            right = right.next

        # Converge from both ends
        while left != right and right.next != left:
            total = left.data + right.data

            if total == target:
                result.append((left.data, right.data))
                left = left.next
                right = right.prev
            elif total < target:
                left = left.next
            else:
                right = right.prev

        return result
class Solution {
    public ArrayList<ArrayList<Integer>> findPairsWithGivenSum(Node head, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        // Place left at head, right at tail
        Node left = head;
        Node right = head;
        while (right.next != null) {
            right = right.next;
        }

        // Converge from both ends
        while (left != right && right.next != left) {
            int sum = left.data + right.data;

            if (sum == target) {
                ArrayList<Integer> pair = new ArrayList<>();
                pair.add(left.data);
                pair.add(right.data);
                result.add(pair);
                left = left.next;
                right = right.prev;
            } else if (sum < target) {
                left = left.next;
            } else {
                right = right.prev;
            }
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

First, we traverse to the tail to initialize the right pointer — this takes O(n). Then, the main loop runs at most n iterations because in each iteration at least one pointer moves inward (left moves right, or right moves left, or both). Once the pointers meet or cross, the loop terminates. Total: O(n) + O(n) = O(n).

Unlike the hashing approach, no sorting of results is needed because the left pointer only moves forward through increasing values, naturally producing pairs in sorted order by the first element.

Space Complexity: O(1)

We use only two pointer variables (left and right) and one integer (sum). No hash set, no auxiliary array, no recursion stack. The only additional memory is the output list itself, which is not counted as auxiliary space.

This makes the two-pointer approach optimal in both time and space — it achieves the theoretical lower bound of O(n) time (every node must be inspected at least once) with the minimum possible O(1) extra space.