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.
This approach utilizes a two-pointer technique taking advantage of the sorted nature of the input array. The first pointer starts at the beginning of the array while the second starts at the end. By evaluating the sum at these two pointers, you can determine how to move the pointers:
This method operates in O(n) time and uses O(1) additional space.
The C solution uses a while loop to implement the two-pointer technique. The left and right pointers are adjusted based on the sum compared to the target, ensuring the correct indices are returned in ascending order due to the sorted nature of the input array.
Time Complexity: O(n)
Space Complexity: O(1)
This approach also takes advantage of the sorted array, integrating binary search for a more theoretically robust approach. For every element in the array, a binary search is employed to find the complement such that the sum is equal to the target:
i.target - numbers[i].The C solution incorporates a binary search helper function to look for the complement of each element from the remaining array indices. Once found, it returns the indices incremented by one, adhering to the input constraints.
Time Complexity: O(n log n) (due to binary search)
Space Complexity: O(1)
Note that the array is sorted in non-decreasing order, so for each numbers[i], we can find the position of target - numbers[i] by binary search, and return [i + 1, j + 1] if it exists.
The time complexity is O(n times log n), where n is the length of the array numbers. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
We define two pointers i and j, which point to the first element and the last element of the array respectively. Each time we calculate numbers[i] + numbers[j]. If the sum is equal to the target value, return [i + 1, j + 1] directly. If the sum is less than the target value, move i to the right by one position, and if the sum is greater than the target value, move j to the left by one position.
The time complexity is O(n), where n is the length of the array numbers. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n) |
| Binary Search Optimization | Time Complexity: O(n log n) (due to binary search) |
| Binary Search | — |
| Two Pointers | — |
| 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 |
TWO SUM II - Amazon Coding Interview Question - Leetcode 167 - Python • NeetCode • 526,921 views views
Watch 9 more video solutions →Practice Two Sum II - Input Array Is Sorted with our built-in code editor and test cases.
Practice on FleetCode