Solve two-sum variants at scale
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: This question evaluates array and hashing algorithms, pair-sum reasoning including duplicate handling and lexicographic minimality, streaming and external-memory algorithm design, trade-offs in time/space complexity, and extension to three-sum with deduplication.
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
Input: ([3, 1, 2, 2, 4], 4)
Expected 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.
Input: ([2, 7, 11, 15], 9)
Expected Output: [0, 1]
Explanation: 2+7=9.
Hints
- A single pass with a hash map from value -> earliest index gives O(n) time.
- Store only the FIRST index at which each value occurs so the matching i is as small as possible.
- 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
Input: ([1, 2, 2, 3, 4], 4)
Expected Output: [0, 3]
Explanation: nums[0]+nums[3]=1+3=4 after the right pointer steps in from value 4.
Input: ([2, 7, 11, 15], 9)
Expected Output: [0, 1]
Explanation: 2+7=9 at the leftmost two elements.
Hints
- Place one pointer at each end and move them inward based on the comparison of the current sum to target.
- 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.
- 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
Input: ([-1, 0, 1, 2, -1, -4], 0)
Expected Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: Classic 3-sum=0: the two distinct triplets after dedup of the repeated -1.
Input: ([0, 0, 0, 0], 0)
Expected Output: [[0, 0, 0]]
Explanation: All zeros yield a single deduplicated triplet.
Hints
- Sort first; then fix the smallest element and run a two-pointer two-sum on the remaining suffix.
- Skip duplicate values for the fixed index to avoid emitting the same triplet from a different starting position.
- After recording a match, advance the left pointer past equal values and retreat the right pointer past equal values to deduplicate.