Two Sum II - Input Array Is Sorted

Two Sum II - Input Array Is Sorted

What is this problem about?

"Two Sum II" is the "Low Space" version of the original Two Sum. You are given an array of integers that is already sorted in non-decreasing order. You need to find two numbers that add up to a specific target. Because the array is sorted, you can solve this without using a Hash Map, achieving $O(1)$ extra space complexity. This problem is about navigating a sorted search space efficiently.

Why is this asked in interviews?

This "Two Sum II interview question" is a favorite at Microsoft and Meta because it tests if a candidate can optimize for memory. Interviewers want to see the "Two Pointers" strategy in action. It demonstrates that you don't just rely on standard data structures like maps, but you can also use the inherent properties of the data (like sorting) to your advantage. It's a key skill for systems where memory is at a premium.

Algorithmic pattern used

The "Array, Two Pointers, Binary Search interview pattern" is the standard solution. You place a left pointer at index 0 and a right pointer at the last index.

• If nums[left] + nums[right] == target, return the indices.
• If the sum is too small, move left to the right to increase it.
• If the sum is too large, move right to the left to decrease it. Since the array is sorted, this "squeezing" motion is guaranteed to find the pair if it exists.

Example explanation

nums = [1, 3, 4, 6, 8, 10], target = 10

1. L=1, R=10. Sum=11. (Too big, move R)
2. L=1, R=8. Sum=9. (Too small, move L)
3. L=3, R=8. Sum=11. (Too big, move R)
4. L=3, R=6. Sum=9. (Too small, move L)
5. L=4, R=6. Sum=10. Found it! Result: Indices [3, 4] (assuming 0-based indexing).

Common mistakes candidates make

A frequent mistake is still using a Hash Map, which wastes $O(N)$ space. Another error is not moving the pointers correctly (e.g., moving both at once), which can skip the target. Some candidates also forget that the array is 1-indexed in some versions of this problem and return the wrong index values.

Interview preparation tip

Master the "Two Pointers" logic for the "Two Sum II coding problem." It's one of the most reusable patterns in technical interviews. Also, mention that while you could use binary search for each element ($O(N \log N)$), the two-pointer approach is better ($O(N)$).