Two Sum II - Input Array Is Sorted
MedPrompt
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] <= 1000numbersis sorted in non-decreasing order.-1000 <= target <= 1000- The tests are generated such that there is exactly one solution.
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to check every possible pair of numbers in the array to see if they sum up to the target. This is done using two nested loops.
Algorithm
- Use a nested loop structure. The outer loop iterates from the first element to the second-to-last element with index
i. - The inner loop iterates from the element after
ito the last element with indexj. - Inside the inner loop, check if
numbers[i] + numbers[j]equals thetarget. - If the sum is equal to the target, we have found our pair. Return a new array containing their 1-based indices,
[i + 1, j + 1]. - Since the problem guarantees that exactly one solution exists, we are sure to find a pair and return from within the loops.
Walkthrough
This method involves iterating through each element of the array and then, for each element, iterating through the rest of the array to find a pair that sums to the target.
For an element at index i, we search for another element at index j (where j > i) such that numbers[i] + numbers[j] == target. While simple, this approach is computationally expensive as it checks every possible pair.
class Solution { public int[] twoSum(int[] numbers, int target) { for (int i = 0; i < numbers.length; i++) { for (int j = i + 1; j < numbers.length; j++) { if (numbers[i] + numbers[j] == target) { return new int[]{i + 1, j + 1}; } } } // This part is unreachable because a solution is guaranteed. return new int[]{-1, -1}; }}Complexity
Time
O(n^2)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Works for unsorted arrays as well.
Cons
Highly inefficient, leading to a "Time Limit Exceeded" error on larger datasets.
Fails to utilize the key information that the input array is sorted.
A better approach leverages the fact that the array is sorted. For each element numbers[i], we can search for its complement (target - numbers[i]) in the rest of the array using binary search, which is much faster than a linear scan.
Algorithm
- Iterate through the array with an index
ifrom0ton-1. - For each
numbers[i], calculatecomplement = target - numbers[i]. - Perform a binary search for
complementin the subarray to the right ofi, i.e., from indexi + 1ton - 1. - If the binary search finds the
complementat indexj, we have found our pair and can return[i + 1, j + 1].
Walkthrough
We can improve upon the brute-force approach by utilizing the sorted nature of the array. We iterate through the array with a single loop. For each element numbers[i], we determine the value we need to find, which is complement = target - numbers[i]. Instead of scanning linearly for this complement, we can use the much more efficient binary search algorithm on the remainder of the array (from index i+1 onwards).
class Solution { public int[] twoSum(int[] numbers, int target) { for (int i = 0; i < numbers.length; i++) { int complement = target - numbers[i]; int low = i + 1; int high = numbers.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (numbers[mid] == complement) { return new int[]{i + 1, mid + 1}; } else if (numbers[mid] < complement) { low = mid + 1; } else { high = mid - 1; } } } // Unreachable code as a solution is guaranteed. return new int[]{-1, -1}; }}Complexity
Time
O(n log n)
Space
O(1)
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Correctly utilizes the sorted property of the array.
Cons
Not the most optimal solution as a linear time solution exists.
The most optimal approach uses two pointers, one starting at the beginning of the array and the other at the end. By comparing the sum of the values at these pointers with the target, we can intelligently move the pointers inwards to find the solution in a single pass.
Algorithm
- Initialize a pointer
leftto0and a pointerrightton-1. - While
left < right:- Calculate
sum = numbers[left] + numbers[right]. - If
sum == target, we found the pair. Return[left+1, right+1]. - If
sum < target, the sum is too small. We need a larger number, so we incrementleft. - If
sum > target, the sum is too large. We need a smaller number, so we decrementright.
- Calculate
Walkthrough
This is the most efficient solution and fully exploits the sorted property of the array. We use two pointers, left starting at the first element (index 0) and right starting at the last element (index n-1).
We then check the sum of the values at these two pointers:
- If
numbers[left] + numbers[right]equals thetarget, we have found our solution. - If the sum is less than the
target, we need a larger sum. Since the array is sorted, we can achieve this by moving theleftpointer to the right (left++), which points to a larger value. - If the sum is greater than the
target, we need a smaller sum. We move therightpointer to the left (right--), which points to a smaller value.
We repeat this process until the pointers meet. Since a solution is guaranteed, we will find the pair before left and right cross.
class Solution { public int[] twoSum(int[] numbers, int target) { int left = 0; int right = numbers.length - 1; while (left < right) { int currentSum = numbers[left] + numbers[right]; if (currentSum == target) { return new int[]{left + 1, right + 1}; } else if (currentSum < target) { left++; } else { // currentSum > target right--; } } // Unreachable code as a solution is guaranteed. return new int[]{-1, -1}; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Optimal time complexity, as it requires only a single pass through the array.
Optimal space complexity, meeting the problem's constraint of constant extra space.
Elegant and easy to implement.
Cons
This approach is only applicable because the input array is sorted.
Solutions
Solution
class Solution {public int[] twoSum(int[] numbers, int target) { for (int i = 0, j = numbers.length - 1;;) { int x = numbers[i] + numbers[j]; if (x == target) { return new int[]{i + 1, j + 1}; } if (x < target) { ++i; } else { --j; } } }}/** * @param {number[]} numbers * @param {number} target * @return {number[]} */ var twoSum = function (numbers, target) { for (let i = 0, j = numbers.length - 1; ; ) { const x = numbers[i] + numbers[j]; if (x === target) { return [i + 1, j + 1]; } if (x < target) { ++i; } else { --j; } } };class Solution {public: vector<int> twoSum(vector<int> &numbers, int target) { for (int i = 0, j = numbers.size() - 1;;) { int x = numbers[i] + numbers[j]; if (x == target) { return {i + 1, j + 1}; } if (x < target) { ++i; } else { --j; } } }};class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: i, j = 0, len(numbers) - 1 while i < j: x = numbers[i] + numbers[j] if x == target: return [i + 1, j + 1] if x < target: i += 1 else: j -= 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.