Find pairs with a given sum in a sorted doubly linked list
Problem
Given a sorted doubly linked list of distinct values and a target x, return every pair of nodes whose values sum to x. Use O(1) extra space.
Example 1
Input: 1 ⇄ 2 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 8 ⇄ 9, x = 7 Output: (1, 6), (2, 5)
Also asked as: Find pairs with a given sum in a DLL
Test cases
Case 1
Input: [1,2,4,5,6,8,9], 7 Expected (any order): [[1,6],[2,5]]
Case 2
Input: [1,5,6], 6 Expected (any order): [[1,5]]
Case 3
Input: [1,2,3], 10 Expected (any order): []
Case 4
Input: [4], 8 Expected (any order): []
View solutionHide solution1 approach
1. Two pointers from both ends
Time O(n)Space O(1)
Start one pointer at head, one at tail. Move them inward based on whether the pair sum is below or above the target.
function pairsWithSum(head, target) { let tail = head; while (tail && tail.next) tail = tail.next; let lo = head, hi = tail; const res = []; while (lo && hi && lo !== hi && hi.next !== lo) { const s = lo.val + hi.val; if (s === target) { res.push([lo.val, hi.val]); lo = lo.next; hi = hi.prev; } else if (s < target) lo = lo.next; else hi = hi.prev; } return res;}