Two Sum II - Input Array Is Sorted
Problem
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. Return the indices of the two numbers as an integer array [index1, index2] of length 2, where 1 <= index1 < index2 <= numbers.length. You may assume that each input would have exactly one solution and you may not use the same element twice.
- 2 ≤ numbers.length ≤ 3 * 10⁴
- −1000 ≤ numbers[i] ≤ 1000
- numbers is sorted in non-decreasing order
- −1000 ≤ target ≤ 1000
- Exactly one valid answer exists
Example
numbers = [2,7,11,15], target = 9[1, 2]Starting with pointers at the beginning (index 0) and end (index 3) of the array, the algorithm calculates the sum: 2 + 15 = 17, which is greater than the target 9. Since the array is sorted, decreasing the right pointer moves to a smaller number. Moving right pointer from index 3 to 2, sum becomes 2 + 11 = 13, still greater than 9. Move right pointer again to index 1, sum is 2 + 7 = 9, which matches the target. The algorithm returns [1, 2] (1-indexed). The critical insight is that the sorted property allows discarding one pointer at each step, avoiding a quadratic search.
Approach
Straightforward Solution
A brute-force approach checks all pairs with nested loops, resulting in O(n^2) time complexity, which is inefficient for large arrays.
Core Observation
Because the array is sorted, the sum of two numbers can be compared to the target to decide which pointer to move. If the sum is too large, moving the right pointer left decreases the sum; if too small, moving the left pointer right increases the sum.
Path to Optimal
The sorted property enables a two-pointer approach. Initialize one pointer at the start and one at the end. Calculate the sum. If sum > target, move the right pointer left to reduce sum. If sum < target, move the left pointer right to increase sum. Repeat until the sum equals the target. This reduces time complexity to O(n).
Optimal Approach
Use two pointers, left and right, starting at the array's ends. In each iteration, compute the sum of numbers[left] and numbers[right]. If sum equals target, return the 1-based indices. If sum is greater than target, decrement right pointer. If sum is less than target, increment left pointer. This guarantees finding the solution in a single pass with O(n) time and O(1) space.
Time
O(n)
Each pointer moves at most n times, resulting in a single linear pass through the array.
Space
O(1)
Only two pointer variables and a few auxiliary variables are used, independent of input size.
Pattern Spotlight
Two Pointers (Greedy Contraction)
The logic of any optimal Two Pointers solution lies in finding the condition that allows you to permanently discard one end of the search space by moving the pointer that is the current 'limiting factor' to the solution.
Solution
| 1 | class Solution:
|
| 2 | def twoSum(self, numbers: list[int], target: int) -> list[int]:
|
| 3 | l, r = 0, len(numbers) - 1
|
| 4 |
|
| 5 | while l < r:
|
| 6 | current_sum = numbers[l] + numbers[r]
|
| 7 |
|
| 8 | if current_sum > target:
|
| 9 | r -= 1
|
| 10 | elif current_sum < target:
|
| 11 | l += 1
|
| 12 | else:
|
| 13 | return [l + 1, r + 1] |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public int[] twoSum(int[] numbers, int target) { |
| 5 | int l = 0, r = numbers.length - 1; |
| 6 | while (l < r) { |
| 7 | int currentSum = numbers[l] + numbers[r]; |
| 8 | if (currentSum > target) { |
| 9 | r--; |
| 10 | } else if (currentSum < target) { |
| 11 | l++; |
| 12 | } else { |
| 13 | return new int[] {l + 1, r + 1}; |
| 14 | } |
| 15 | } |
| 16 | return new int[0]; |
| 17 | } |
| 18 | } |
| 1 | #include <vector> |
| 2 | using namespace std; |
| 3 | |
| 4 | class Solution { |
| 5 | public: |
| 6 | vector<int> twoSum(vector<int>& numbers, int target) { |
| 7 | int l = 0, r = (int)numbers.size() - 1; |
| 8 | while (l < r) { |
| 9 | int currentSum = numbers[l] + numbers[r]; |
| 10 | if (currentSum > target) { |
| 11 | r--; |
| 12 | } else if (currentSum < target) { |
| 13 | l++; |
| 14 | } else { |
| 15 | return {l + 1, r + 1}; |
| 16 | } |
| 17 | } |
| 18 | return {}; |
| 19 | } |
| 20 | }; |
| 1 | var twoSum = function(numbers, target) { |
| 2 | let l = 0, r = numbers.length - 1; |
| 3 | while (l < r) { |
| 4 | const currentSum = numbers[l] + numbers[r]; |
| 5 | if (currentSum > target) { |
| 6 | r--; |
| 7 | } else if (currentSum < target) { |
| 8 | l++; |
| 9 | } else { |
| 10 | return [l + 1, r + 1]; |
| 11 | } |
| 12 | } |
| 13 | return []; |
| 14 | }; |
Step-by-Step Solution
Initialize Left and Right Pointers at Array Boundaries
| 3 | l, r = 0, len(numbers) - 1
|
Objective
To set up two pointers at the start and end of the sorted array to begin the search for the target sum.
Key Insight
Starting pointers at the extremes leverages the sorted order to evaluate the largest and smallest elements first, enabling a greedy contraction of the search space based on the sum comparison with the target.
Interview Quick-Check
Core Logic
Initializing pointers at the array boundaries sets the widest possible range to evaluate sums, enabling efficient contraction.
State & Boundaries
Pointers must be valid indices within the array, starting at 0 and len(numbers) - 1.
Iteratively Adjust Pointers Based on Sum Comparison
| 5 | while l < r:
|
| 6 | current_sum = numbers[l] + numbers[r]
|
| 8 | if current_sum > target:
|
| 9 | r -= 1
|
| 10 | elif current_sum < target:
|
| 11 | l += 1
|
Objective
To move pointers inward based on whether the current sum is greater or less than the target, narrowing down to the correct pair.
Key Insight
Because the array is sorted, if the sum is too large, moving the right pointer left decreases the sum; if too small, moving the left pointer right increases the sum. This greedy adjustment ensures no valid pairs are skipped and the search space shrinks each iteration.
Interview Quick-Check
Core Logic
The sum comparison guides pointer movement: decrement right if sum too large, increment left if sum too small, ensuring convergence to the target sum.
State & Boundaries
The loop continues while left pointer is less than right pointer, ensuring distinct elements.
Common Pitfalls & Bugs
Failing to update pointers correctly or using <= instead of < in the loop condition can cause infinite loops or incorrect results.
Return 1-Based Indices of the Found Pair
| 12 | else:
|
| 13 | return [l + 1, r + 1] |
Objective
To return the indices of the two numbers that sum to the target, adjusted for 1-based indexing as required by the problem.
Key Insight
The problem specifies 1-based indexing, so the zero-based pointers must be incremented by one before returning. Returning immediately upon finding the pair ensures optimal time complexity.
Interview Quick-Check
Core Logic
Returning the adjusted indices immediately upon finding the target sum terminates the search efficiently.
State & Boundaries
Indices must satisfy 1 <= index1 < index2 <= numbers.length.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
l, r = 0, len(numbers) - 1Initialize left and right pointers at the start and end of the array.
Setting pointers at the array boundaries leverages the sorted order to evaluate the largest and smallest elements first, enabling efficient contraction of the search space.
while l < r:Begin a loop that continues while left pointer is less than right pointer.
The loop condition ensures that the two pointers do not cross, maintaining the invariant that the pointers reference distinct elements.
current_sum = numbers[l] + numbers[r]Calculate the sum of the elements at the left and right pointers.
Computing the current sum is essential to decide how to adjust the pointers to approach the target.
if current_sum > target:Check if the current sum is greater than the target.
If the sum is too large, the right pointer must move left to reduce the sum, exploiting the sorted order.
r -= 1Move the right pointer one step to the left.
Decrementing the right pointer reduces the sum by selecting a smaller number, moving closer to the target.
elif current_sum < target:Check if the current sum is less than the target.
If the sum is too small, the left pointer must move right to increase the sum.
l += 1Move the left pointer one step to the right.
Incrementing the left pointer increases the sum by selecting a larger number, moving closer to the target.
else:Return the 1-based indices of the two numbers that sum to the target.
Returning immediately upon finding the correct pair ensures optimal time complexity and satisfies the problem's 1-based indexing requirement.
return [l + 1, r + 1]Adjust zero-based indices to 1-based before returning.
The problem specifies 1-based indexing, so adding one to each pointer aligns the output with the problem constraints.
Test Your Understanding
Why does moving the pointer at the side that causes the sum to be too large or too small guarantee finding the solution without missing any valid pairs?
Because the array is sorted, moving the pointer at the side that causes the sum to be off adjusts the sum in the correct direction without skipping any potential valid pairs, ensuring all possibilities are explored efficiently.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Two Sum II - Input Array Is Sorted from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Two Sum II - Input Array Is Sorted drill