Find pairs with a given sum in a sorted doubly linked list

Easy

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): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}