255. Find Pairs With a Given Sum in a Doubly Linked List

A doubly linked list contains n values sorted in ascending order. Given a target sum X, find pairs of values that add up to X using the two-pointer technique: start one pointer at the front and one at the back, and move them toward each other. Print each pair found as 'a b' (a from the front pointer, b from the back pointer) on its own line, in the order the two pointers find them. If no pair sums to X, print -1.

Input: The first line contains an integer n. The second line contains n space-separated integers sorted ascending, the doubly linked list's values. The third line contains the target sum X. Output: Print each found pair as 'a b' on its own line, in the order the two-pointer scan finds them; print -1 if no pair sums to X.

2 <= n <= 10^5

This is the linked-list version of the classic 'pair with given sum in a sorted array' two-pointer technique - made practical here specifically because the DOUBLY linked list supports O(1) backward movement, unlike a singly linked list.

In a sorted doubly linked list, find pairs of values that add up to a given target. Brute force: Check every possible pair of nodes directly - this costs O(n²), unnecessary given the list's sorted order and the ability to walk both directions. Optimised: A doubly linked list lets you walk from BOTH ends simultaneously in O(1) per step (something a singly linked list couldn't support efficiently from the back) - this is exactly what the two-pointer technique needs, finding all pairs in a single combined linear pass.

For every node in the list, walk through every other node and check if the two values sum to X, printing each qualifying pair. This checks all possible pairs directly and is correct, but re-scanning the remainder of the list for every node makes it quadratic, and it also ignores that the list is already sorted. Time: O(n^2) Space: O(1)

Traverse the list once, and for each value v, check whether X - v has already been seen using a hash set; if so, report the pair, otherwise insert v into the set and continue. This finds all pairs in a single pass by trading extra memory for time, but it does not exploit the sorted order the way the required two-pointer technique does, and it can report pairs in a different order than 'front pointer meets back pointer'. Time: O(n) Space: O(n)

Since the doubly linked list is sorted, place one pointer at the head and one at the tail. If the sum of their values equals X, record the pair and move both pointers inward; if the sum is less than X, advance the front pointer (to increase the sum); if it is greater, retreat the back pointer (to decrease the sum). Each comparison eliminates at least one node from consideration, so the whole list is scanned only once, using the doubly linked list's backward links instead of any extra storage. Time: O(n) Space: O(1)

1. Start one pointer at the FRONT of the list and one at the BACK. 2. If the pair's sum is too SMALL, advance the front pointer forward; if too BIG, move the back pointer backward; if it MATCHES, record the pair and move both pointers inward. 3. Stop as soon as the two pointers meet or cross.

Time: O(n) - the two pointers together traverse the list once. Space: O(1) extra space beyond the two pointers.

n = 2 (the minimum size), no pair summing to X (print -1), and values where multiple valid pairs exist as the pointers converge.

Be ready to explain why this technique specifically REQUIRES a doubly linked list (or an array) - a plain singly linked list can't efficiently walk backward from the tail, which is essential for the two-pointer approach here.