1034. Two-Way Pair Finder
A coupon app stores item prices in a doubly linked list sorted in non-decreasing order. Given head and an integer target, find every distinct pair of values [a, b] with a <= b such that a + b equals target and the two values come from two different nodes.
Return the pairs as a 2D array sorted by a ascending. Each distinct value pair appears once, even if the values repeat in the list. Return an empty array when no pair exists. Use O(n) time and O(1) extra space apart from the answer; sums must not overflow 32 bits.
Example 1
- Input:
- head = [1,2,4,5,7,9], target = 9
- Output:
- [[2,7],[4,5]]
- Explanation:
2 + 7 and 4 + 5 both give 9; 1 + 9 is 10 and so does not count.
Example 2
- Input:
- head = [-3,-1,0,1,3,4], target = 1
- Output:
- [[-3,4],[0,1]]
- Explanation:
-3 + 4 and 0 + 1 reach 1; -1 would need a 2, which is absent.
Constraints
0 ≤ list length n ≤ 105
-109 ≤ node value ≤ 109, values sorted in non-decreasing order
-109 ≤ target ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)