L19: Find all Pairs with given Sum in DLL

This chapter explores how to efficiently find all unique pairs of elements in a sorted Doubly Linked List (DLL) that add up to a specific target sum. We will examine the transition from a naive nested-traversal approach ($O(N^2)$) to an optimal two-pointer approach ($O(N)$ time, $O(1)$ auxiliary space) by leveraging the inherent properties of sorted doubly linked lists.

1. Why Do We Need This? (Problem Statement & Status Quo)

Given the head of a sorted doubly linked list and a target sum, our goal is to return all valid pairs of node values whose sum equals the target.

• Input Example:
  • DLL: 1 <-> 2 <-> 3 <-> 4 <-> 9
  • Target Sum: 5
• Output:
  • Valid pairs: (1, 4) and (2, 3) (order does not matter).
  • Invalid pairs: (2, 9) because $2 + 9 = 11 \neq 5$.

The challenge in a linked list compared to an array is that we do not have random index access ($O(1)$ lookups via indices like arr[i]). However, because the doubly linked list is sorted and bidirectional, we can navigate both forward and backward.

2. Core Mental Model & The Sorted Advantage

Real-Life Analogy: The Two-End Balancing Scale

Imagine you have a row of people arranged strictly by height from shortest to tallest. You are asked to find pairs of people whose combined age equals a target number.

• If you pick the shortest person (at the very beginning) and the tallest person (at the very end) and their combined age is too high, you instantly know that keeping the tallest person and pairing them with anyone shorter will result in an even higher sum. Therefore, you must move your tall marker one step inward toward shorter heights.
• Conversely, if their combined sum is too low, moving the tall marker inward won't help; you must move your short marker one step upward toward taller heights.

In a sorted doubly linked list, we can place one pointer at the head (start) and another pointer at the tail (end), moving them inward based on our running sum comparison.

3. Naive Approach: Nested Traversal ($O(N^2)$)

The most intuitive brute-force solution is to use two pointers (temp1 and temp2) to evaluate every possible pair combination.

Step-by-Step Execution of Naive Approach

1. Initialize temp1 at the head.
2. Initialize temp2 at temp1.next.
3. Traverse temp2 forward while temp2 is not null:
   • Compute sum = temp1.val + temp2.val.
   • If sum == target, store the pair in our result data structure.
   • Early Stopping Optimization: Because the DLL is sorted, the moment sum > target, any subsequent node to the right of temp2 will have an even larger value. We can immediately break the inner loop and advance temp1.
4. Move temp1 to temp1.next and repeat.

Naive Pseudo-Code

def findPairsNaive(head, target):
    ans = []
    temp1 = head
    
    while temp1 is not None:
        temp2 = temp1.next
        while temp2 is not None:
            current_sum = temp1.val + temp2.val
            
            if current_sum == target:
                ans.append((temp1.val, temp2.val))
                temp2 = temp2.next
            elif current_sum < target:
                temp2 = temp2.next
            else:
                # Exceeded target in a sorted list; no need to continue inner loop
                break
                
        temp1 = temp1.next
        
    return ans

Limitations of the Naive Approach

• Time Complexity: In the worst-case scenario (e.g., all pairs sum up or need full scanning), the outer loop runs $N$ times and the inner loop runs roughly $N$ times, leading to $O(N^2)$ time complexity.
• Space Complexity: $O(1)$ auxiliary space (excluding space required to store the output answers).

4. Optimal Approach: Two-Pointer Technique ($O(N)$)

Since the interviewer will reject the $O(N^2)$ solution, we must utilize the sorted property and the bidirectional nature of the doubly linked list to achieve optimal performance.

How the Two-Pointer Strategy Works

1. Left Pointer: Starts at the head of the DLL.
2. Right Pointer: Starts at the tail of the DLL (found via a quick traversal).
3. Condition Check: Continue while left.val < right.val (meaning pointers have not crossed or met):
   • Case 1 (left.val + right.val == target): We found a valid pair! Add (left.val, right.val) to our results list. Then, advance left forward (left = left.next) and move right backward (right = right.prev).
   • Case 2 (left.val + right.val < target): Our sum is too small. To increase the sum, we need a larger value. Move left forward (left = left.next).
   • Case 3 (left.val + right.val > target): Our sum is too large. To decrease the sum, we need a smaller value. Move right backward (right = right.prev).

5. Complete Flow Walkthrough

Let's trace the optimal two-pointer algorithm with:

• DLL: 1 <-> 2 <-> 3 <-> 4 <-> 9
• Target: 5

6. Optimal Implementation (Pseudo-Code)

Below is the structured pseudo-code demonstrating the helper function to find the tail and the main two-pointer search routine.

def findTail(head):
    tail = head
    while tail.next is not None:
        tail = tail.next
    return tail

def findPairsWithGivenSum(head, target):
    ans = []
    if head is None:
        return ans
        
    left = head
    right = findTail(head)
    
    # Traverse until pointers meet or cross
    while left != right and right.next != left:
        current_sum = left.val + right.val
        
        if current_sum == target:
            ans.append((left.val, right.val))
            left = left.next
            right = right.prev
        elif current_sum < target:
            left = left.next
        else:
            right = right.prev
            
    return ans

7. Complexity Analysis

8. Summary and Key Takeaways

• Exploit Sorted Order: Always inspect if a problem statement mentions "sorted" data structures; it usually hints at binary search or two-pointer techniques.
• Bidirectional Advantage: Unlike singly linked lists where backward traversal requires $O(N)$ extra work or hash maps, doubly linked lists allow $O(1)$ backward movement via .prev pointers.
• Pointer Initialization: Set left at the head and right at the computed tail.
• Inward Convergence: Increment left when the sum is too small, and decrement right when the sum is too large.
• Termination Condition: Stop when left == right or when right crosses left (right.next == left).
• Optimal Efficiency: The two-pointer approach reduces time complexity from $O(N^2)$ down to linear $O(N)$ time with $O(1)$ extra space.