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 460,623 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 receive a sorted array of integers and a target value. Your task is to return the 1-indexed positions of two numbers whose sum equals the target. The sorted property of the array changes how you approach the classic Two Sum problem and allows more efficient strategies than a hash map.
Approach 1: Two-Pointer Technique (O(n) time, O(1) space)
This approach takes advantage of the sorted order of the array. Start one pointer at the beginning and another at the end. Compute the sum of the two numbers. If the sum is greater than the target, move the right pointer left to reduce the value. If the sum is smaller, move the left pointer right to increase it. Continue until the sum matches the target. Because each step moves one pointer inward, the array is scanned at most once, giving O(n) time and constant O(1) space.
The key insight is monotonic behavior: moving the left pointer increases the sum, while moving the right pointer decreases it. This makes the two-pointer scan deterministic and efficient. Problems involving sorted arrays often use this pattern, especially when searching for pairs or ranges. See more patterns in two pointers and array problems.
Approach 2: Binary Search Optimization (O(n log n) time, O(1) space)
Iterate through the array and treat each number as the first element of the pair. For each index i, compute the required complement target - numbers[i]. Since the array is sorted, perform a binary search in the subarray to the right of i to find that complement. Binary search runs in O(log n), and repeating it for all n elements results in O(n log n) time with constant extra space.
This approach is useful when you want to explicitly demonstrate knowledge of binary search on sorted arrays. The logic remains straightforward: iterate, compute complement, and run binary search on the remaining range. More examples appear in binary search problems.
Recommended for interviews: The two-pointer technique is the expected solution because it achieves optimal O(n) time with O(1) space and directly leverages the sorted array property. Interviewers typically expect you to recognize this pattern quickly. Showing the binary search alternative demonstrates understanding of sorted array strategies, but the two-pointer solution reflects stronger algorithmic intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n) | O(1) | Best when the array is already sorted and you need the optimal linear-time solution |
| Binary Search per Element | O(n log n) | O(1) | When demonstrating binary search on sorted arrays or when practicing search-based patterns |