Find Pairs with a Given Sum in a DLL

Problem Statement

Given a sorted doubly linked list of positive integers and a target sum, find all pairs of nodes whose sum equals the target. Each pair should be returned in order, and no element should be used twice.

Example

Input: 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9, target = 7
Output: [(1, 6), (2, 5)]

Input: 1 <-> 5 <-> 6, target = 6
Output: [(1, 5)]

Brute Force Approach

Intuition

The brute force approach checks every possible pair in the list. For each node, we traverse all subsequent nodes and check if their sum equals the target.

Algorithm

Use two nested loops
For each node (outer loop), traverse all nodes after it (inner loop)
If the sum of two nodes equals target, add the pair to result
Continue until all pairs are checked

Code

java

import java.util.ArrayList;
import java.util.List;

class Node {
    int data;
    Node prev;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

public class DLLPairs {
    public static List<int[]> findPairsBruteForce(Node head, int target) {
        List<int[]> result = new ArrayList<>();
        
        if (head == null) return result;
        
        Node first = head;
        
        while (first != null) {
            Node second = first.next;
            
            while (second != null) {
                int sum = first.data + second.data;
                
                if (sum == target) {
                    result.add(new int[]{first.data, second.data});
                }
                
                // Since list is sorted, if sum > target, no need to check further
                if (sum > target) {
                    break;
                }
                
                second = second.next;
            }
            
            first = first.next;
        }
        
        return result;
    }
    
    public static void printPairs(List<int[]> pairs) {
        System.out.print("[");
        for (int i = 0; i < pairs.size(); i++) {
            System.out.print("(" + pairs.get(i)[0] + ", " + pairs.get(i)[1] + ")");
            if (i < pairs.size() - 1) System.out.print(", ");
        }
        System.out.println("]");
    }
}

Complexity Analysis

Time Complexity: O(n²) - Nested loops checking all pairs
Space Complexity: O(1) - Only using constant extra space (excluding output)

Optimal Approach

Intuition

Since the doubly linked list is sorted, we can use the two-pointer technique. We place one pointer at the beginning (left) and one at the end (right). If the sum is less than target, we move left forward. If sum is greater, we move right backward. If equal, we found a pair.

Algorithm

Initialize left pointer to head and right pointer to tail
While left is before right:
- Calculate sum of left and right values
- If sum equals target, add pair and move both pointers
- If sum is less than target, move left forward
- If sum is greater than target, move right backward
Return all found pairs

Code

java

import java.util.ArrayList;
import java.util.List;

class Node {
    int data;
    Node prev;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

public class DLLPairsOptimal {
    public static List<int[]> findPairsOptimal(Node head, int target) {
        List<int[]> result = new ArrayList<>();
        
        if (head == null) return result;
        
        // Find the tail (rightmost node)
        Node left = head;
        Node right = head;
        while (right.next != null) {
            right = right.next;
        }
        
        // Two pointer technique
        while (left != right && left.prev != right) {
            int sum = left.data + right.data;
            
            if (sum == target) {
                result.add(new int[]{left.data, right.data});
                left = left.next;
                right = right.prev;
            }
            else if (sum < target) {
                left = left.next;
            }
            else {
                right = right.prev;
            }
        }
        
        return result;
    }
    
    public static void printPairs(List<int[]> pairs) {
        System.out.print("[");
        for (int i = 0; i < pairs.size(); i++) {
            System.out.print("(" + pairs.get(i)[0] + ", " + pairs.get(i)[1] + ")");
            if (i < pairs.size() - 1) System.out.print(", ");
        }
        System.out.println("]");
    }
}

Complexity Analysis

Time Complexity: O(n) - Single traversal with two pointers
Space Complexity: O(1) - Only using constant extra space (excluding output)

Key Takeaways

Sorted List Advantage: The sorted property allows us to use the two-pointer technique efficiently
Two Pointer on DLL: Unlike arrays, DLL allows backward traversal without extra space, making two-pointer approach natural
Termination Condition: Stop when pointers meet or cross each other
Pointer Movement Logic:
- Sum too small → move left forward (increase sum)
- Sum too large → move right backward (decrease sum)
- Sum equals target → record pair and move both
Finding Tail: We need O(n) time initially to find the tail, but the overall algorithm remains O(n)

Find pairs with a given sum in a DLL

Find Pairs with a Given Sum in a DLL

Problem Statement

Example

Brute Force Approach

Intuition

Algorithm

Code

Complexity Analysis

Optimal Approach

Intuition

Algorithm

Code

Complexity Analysis

Key Takeaways