Watch 10 video solutions for Two Sum II - Input Array Is Sorted, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by NeetCode has 526,921 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
Constraints:
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers is sorted in non-decreasing order.-1000 <= target <= 1000Problem Overview: You get a 1-indexed sorted array of integers and a target value. Return the indices of the two numbers whose sum equals the target. Exactly one valid pair exists, and you cannot reuse the same element.
Approach 1: Two-Pointer Technique (O(n) time, O(1) space)
The sorted property of the array allows a classic two pointers strategy. Start one pointer at the leftmost index and another at the rightmost index. Compute the sum of both values. If the sum equals the target, return the indices. If the sum is smaller than the target, move the left pointer right to increase the sum. If the sum is larger, move the right pointer left to decrease it.
This works because the array is already sorted, so moving pointers predictably increases or decreases the sum. Every iteration eliminates one candidate pair, which guarantees linear traversal. You scan the array at most once, giving O(n) time complexity and constant O(1) extra space. This is the optimal and most common interview solution for problems involving a sorted array.
Approach 2: Binary Search Optimization (O(n log n) time, O(1) space)
Another option leverages binary search. Iterate through the array with index i. For each element numbers[i], compute the complement target - numbers[i]. Because the array is sorted, run binary search on the remaining subarray [i+1, n-1] to check whether that complement exists.
Each binary search takes O(log n) time, and you perform it for up to n elements. That leads to O(n log n) total time with constant O(1) extra space. This approach is conceptually straightforward if you're already comfortable with binary search patterns, but it performs more comparisons than the two-pointer strategy.
The key insight is recognizing that the sorted order enables efficient searching for the complementary value. However, because you restart a binary search for every element, the runtime grows faster than the linear two-pointer solution.
Recommended for interviews: The two-pointer approach is the expected answer. Interviewers want you to notice that the input array is sorted and exploit that property to reduce the problem from O(n log n) or O(n^2) to O(n). Mentioning the binary search alternative shows good algorithmic awareness, but implementing the linear two-pointer scan demonstrates stronger problem-solving instincts.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n) | O(1) | Best choice when the array is already sorted and only one pair is guaranteed |
| Binary Search Optimization | O(n log n) | O(1) | Useful when practicing binary search patterns on sorted arrays |