Given a sorted doubly linked list and a target sum, find all pairs of nodes whose sum equals the target.\u00a0Return the pairs as a list of lists, where each inner list contains two elements representing a valid pair.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Example 1:<\/strong><\/p>\n\n\n\n Example 2:<\/strong><\/p>\n\n\n\n Your Task:<\/strong> Expected Time Complexity:<\/strong> O(N) 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.<\/p>\n\n\n\nInput: <\/strong>\n1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9\ntarget = 7\nOutput: <\/strong>(1, 6), (2,5)\nExplanation: <\/strong>We can see that there are two pairs \n(1, 6) and (2,5) with sum 7.<\/pre>\n\n\n\n
Input: <\/strong>
1 <-> 5 <-> 6
target = 6
Output: <\/strong>(1,5)
Explanation: <\/strong>We can see that there is one pairs (1, 5) with sum 6.<\/pre>\n\n\n\n
You don’t need to read input or print anything. Your task is to complete the function findPairsWithGivenSum() <\/strong>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.<\/p>\n\n\n\n
Expected Auxiliary Space:<\/strong> O(1)
Constraints:<\/strong>
1 <= N <= 105<\/sup>
1 <= target <= 105<\/sup><\/p>\n\n\n
\n\n\n\nSolution: Optimal Approach (Two Pointers)<\/h2>\n\n\n\n
Intuition<\/h3>\n\n\n\n
Detailed Approach<\/h3>\n\n\n\n
\n
Code<\/h3>\n\n\n\n