Solve two-sum variants at scale

Base task: Given nums = [3, 1, 2, 2, 4] and target = 4, return the 0-based index pair (i, j) with i < j such that nums[i] + nums[j] = target. If multiple pairs exist, return the lexicographically smallest (i, j). Achieve expected O(n) time and O(n) extra space; justify correctness for duplicates. Follow-ups:

1. If nums is already sorted ascending, provide an O(n) time, O(1) space solution and prove minimal lexicographic pair selection still holds.
2. Streaming variant: nums arrives as an unbounded stream and you must answer membership queries two_sum_exists(x) online with sublinear memory. Propose a data structure, update/query costs, and false-positive/false-negative trade-offs if any.
3. Very large array (hundreds of millions of ints) under a 200MB RAM cap. Describe an external-memory or hashing-with-bucketing approach, handling negatives and overflow.
4. Extend to three-sum for a sorted array; give complexity and deduplication strategy.

Two-Sum: lexicographically smallest index pair

Given an integer array nums and an integer target, return the 0-based index pair [i, j] with i < j such that nums[i] + nums[j] == target. If several pairs exist, return the lexicographically smallest pair (smallest i, then smallest j). If no pair exists, return an empty list [].

Achieve expected O(n) time and O(n) extra space. The array is NOT assumed to be sorted and may contain duplicates, zeros, and negatives.

Correctness with duplicates: scan left to right; for each index j, check whether the complement target - nums[j] was already seen at some earlier index i < j. Storing only the FIRST index at which each value appears guarantees the smallest possible i for any matching j, and scanning j in increasing order yields the lexicographically smallest pair overall.

Constraints

• 0 <= len(nums) <= 10^5
• -10^9 <= nums[i], target <= 10^9
• Indices are 0-based and the returned pair must satisfy i < j
• Return [] when no valid pair exists

Examples

Example 1

Input: ([3, 1, 2, 2, 4], 4)
Output: [0, 1]

Explanation: nums[0]+nums[1]=3+1=4. Pair (2,3)=2+2=4 also works but (0,1) is lexicographically smaller.

Example 2

Input: ([2, 7, 11, 15], 9)
Output: [0, 1]

Explanation: 2+7=9.

Hints

1. A single pass with a hash map from value -> earliest index gives O(n) time.
2. Store only the FIRST index at which each value occurs so the matching i is as small as possible.
3. Scanning j from left to right and taking the first complement hit yields the lexicographically smallest (i, j).

Follow-up 1 - Sorted array two-sum in O(1) extra space

The array nums is now guaranteed to be sorted in ascending order. Return an index pair [lo, hi] with lo < hi such that nums[lo] + nums[hi] == target, using O(n) time and O(1) extra space. Return [] if no pair exists.

Use the two-pointer technique: start lo at the left end and hi at the right end. If the sum is too small, increment lo; if too large, decrement hi; on equality, return the pair. Because the array is sorted, every candidate sum is monotone in each pointer move, so no valid pair is ever skipped.

Note on duplicates: the pure O(1)-space two-pointer returns a VALID outermost index pair, not necessarily the lexicographically smallest one. For example, on [1,1,1,1] with target 2 it returns [0,3] (the first equality it meets), which is acceptable here since recovering the absolute-smallest index pair among equal values would require extra bookkeeping and break the O(1)-space guarantee.

Constraints

• nums is sorted in non-decreasing order
• 0 <= len(nums) <= 10^5
• -10^9 <= nums[i], target <= 10^9
• Return [] when no valid pair exists

Examples

Example 1

Input: ([1, 2, 2, 3, 4], 4)
Output: [0, 3]

Explanation: nums[0]+nums[3]=1+3=4 after the right pointer steps in from value 4.

Example 2

Input: ([2, 7, 11, 15], 9)
Output: [0, 1]

Explanation: 2+7=9 at the leftmost two elements.

Hints

1. Place one pointer at each end and move them inward based on the comparison of the current sum to target.
2. Sorted order makes the sum monotone in each move, so a too-small sum means advance the left pointer and a too-large sum means retreat the right pointer.
3. On the first equality you may return immediately; with duplicate values this gives a valid outermost pair, not necessarily the smallest indices.

Follow-up 4 - Three-sum on a sorted array (unique triplets)

Given an integer array nums and an integer target, return all UNIQUE triplets [a, b, c] (as value triplets, each non-decreasing) such that a + b + c == target. No two returned triplets may be the same multiset of values. Return the triplets sorted in ascending order.

Approach: sort nums (O(n log n)), then fix the first element with an outer loop and solve a two-sum on the remaining suffix with the two-pointer technique (O(n) per fix), giving O(n^2) overall. Deduplicate by skipping equal values for the fixed index and, after recording a hit, skipping equal values for both the left and right pointers. This yields each distinct value-triplet exactly once.

Complexity: O(n^2) time, O(1) extra space beyond the sort and output.

Constraints

• 0 <= len(nums) <= 3000
• -10^9 <= nums[i], target <= 10^9
• Triplets are value triplets (multisets), deduplicated
• Each triplet is returned in non-decreasing order and the overall list is sorted ascending

Examples

Example 1

Input: ([-1, 0, 1, 2, -1, -4], 0)
Output: [[-1, -1, 2], [-1, 0, 1]]

Explanation: Classic 3-sum=0: the two distinct triplets after dedup of the repeated -1.

Example 2

Input: ([0, 0, 0, 0], 0)
Output: [[0, 0, 0]]

Explanation: All zeros yield a single deduplicated triplet.

Hints

1. Sort first; then fix the smallest element and run a two-pointer two-sum on the remaining suffix.
2. Skip duplicate values for the fixed index to avoid emitting the same triplet from a different starting position.
3. After recording a match, advance the left pointer past equal values and retreat the right pointer past equal values to deduplicate.