Find pairs with given sum in doubly linked list | GFG Practice | Optimal Solution

Given a sorted doubly linked list and a target sum, find all pairs of nodes whose sum equals the target. Return the pairs as a list of lists, where each inner list contains two elements representing a valid pair.

Here’s the [Problem Link] to begin with.

Example 1:

Input:  
1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9
target = 7
Output: (1, 6), (2,5)
Explanation: We can see that there are two pairs 
(1, 6) and (2,5) with sum 7.

Example 2:

Input: 
1 <-> 5 <-> 6
target = 6
Output: (1,5)
Explanation: We can see that there is one pairs  (1, 5) with sum 6.

Your Task:
You don’t need to read input or print anything. Your task is to complete the function findPairsWithGivenSum() which takes head node of the doubly linked list and an integer target as input parameter and returns an array of pairs. If there is no such pair return empty array.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10⁵
1 <= target <= 10⁵

Solution: Optimal Approach (Two Pointers)

Intuition

Think of this like finding dance partners at a party where everyone is lined up by height! You want pairs whose combined height equals a specific number. The smartest approach is to have one person start from the shortest end and another from the tallest end. If their combined height is too small, the shorter person moves to someone taller. If it’s too big, the taller person moves to someone shorter. If it’s perfect, you found a pair! This is exactly what we do with two pointers in a sorted doubly linked list.

Detailed Approach

1. Set Up Two Pointers: Start with left pointer at the head (smallest element) and right pointer at the tail (largest element)
2. Find the Tail: Move the right pointer to the end of the list to start from the largest element
3. Two Pointer Technique: While left pointer is before right pointer, check their sum
4. Found a Pair: If sum equals target, add the pair to results and move both pointers inward
5. Sum Too Large: If sum is greater than target, move right pointer backward (to smaller element)
6. Sum Too Small: If sum is less than target, move left pointer forward (to larger element)
7. Continue Until Pointers Meet: Stop when pointers meet or cross each other

Code

class Solution:
    def findPairsWithGivenSum(
        self, target: int, head: Optional["Node"]
    ) -> List[List[int]]:
        left = head          # Left pointer starts at head (smallest element)
        right = head         # Right pointer will move to tail (largest element)
        ans = []            # List to store all valid pairs
        
        # Move right pointer to the end of the list
        while right.next:
            right = right.next
        
        # Use two pointers to find pairs
        while left is not None and right is not None and left.data < right.data:
            total = left.data + right.data  # Calculate sum of current pair
            
            if total == target:
                # Found a valid pair, add to results
                ans.append([left.data, right.data])
                left = left.next     # Move left pointer forward
                right = right.prev   # Move right pointer backward
            elif total > target:
                # Sum is too large, move right pointer to smaller element
                right = right.prev
            else:
                # Sum is too small, move left pointer to larger element
                left = left.next
        
        return ans

Code Explanation

This solution uses the classic two-pointer technique optimized for doubly linked lists. We start by positioning the right pointer at the tail of the list. Then we use two pointers moving towards each other from opposite ends. The key insight is that since the list is sorted, we can make intelligent decisions about which pointer to move based on whether the current sum is too large or too small. When the sum equals the target, we found a valid pair and move both pointers inward to look for more pairs.

Dry Run

Let’s trace through: 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9, target = 7

Initial Setup:

• left = 1, right = 9, ans = []

Step 1:

• total = 1 + 9 = 10
• 10 > 7, so move right pointer backward: right = 8

Step 2:

• total = 1 + 8 = 9
• 9 > 7, so move right pointer backward: right = 6

Step 3:

• total = 1 + 6 = 7
• 7 == 7, found pair! ans = []
• Move both pointers: left = 2, right = 5

Step 4:

• total = 2 + 5 = 7
• 7 == 7, found pair! ans = [, ]
• Move both pointers: left = 4, right = 4

Step 5:

• left.data = 4, right.data = 4
• left.data is not < right.data, so loop ends

Result: [[1], ]

Time and Space Complexity

• Time Complexity: O(n) – We visit each node at most once with our two pointers
• Space Complexity: O(1) – We only use a few pointer variables (excluding the result array)

Simplifying It

This approach is like having two people walk towards each other from opposite ends of a sorted line. They check if their combined value matches what we’re looking for. If it’s too big, the person from the high end steps back. If it’s too small, the person from the low end steps forward. If it’s just right, we record the pair and both people move inward to look for more pairs.

Key Insights

Why this works for doubly linked lists:
The doubly linked list structure allows us to move both forward and backward efficiently. This is crucial for the two-pointer technique because we need to move the right pointer backward when the sum is too large.

Why the list needs to be sorted:
The sorting property allows us to make intelligent decisions about which pointer to move. If the sum is too large, we know moving the right pointer backward will give us a smaller sum.

Why we check left.data < right.data:
This condition ensures we don’t count the same pair twice and that we stop when pointers meet or cross each other.

Summary

This optimal solution efficiently finds all pairs in a single pass using the two-pointer technique. The key insight is leveraging the sorted nature of the doubly linked list and the bidirectional traversal capability to implement an elegant solution.

This problem beautifully demonstrates how the structure of doubly linked lists (with both forward and backward pointers) combined with the sorted property can lead to very efficient algorithms. The two-pointer technique is a fundamental approach that appears in many array and linked list problems!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.