Two Sum II - Input Array Is Sorted

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.

10 min read

Time: O(n)

Space: O(1)

Solve on LeetCode

Examples

Input:numbers = [2,7,11,15], target = 9

Output:[1,2]

Explain:

The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Input:numbers = [2,3,4], target = 6

Output:[1,3]

Explain:

The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Problem Understanding

This is similar to the classic Two Sum, but with two key differences:

The array is already sorted.
You must return 1-based indices.

A brute force approach would be to check every pair, which is O(n²). However, the sorted property allows us to use the Two Pointers technique to solve it in linear time O(n).

Algorithm Strategy

Initialize left at the start (index 0) and right at the end (index n-1).
Calculate current_sum = numbers[left] + numbers[right].
If current_sum == target, we found the pair! Return [left + 1, right + 1].
If current_sum < target, we need a larger sum. Since the array is sorted, moving left to the right increases the sum.
If current_sum > target, we need a smaller sum. Moving right to the left decreases the sum.

Interactive Visualization

Step 1 / 1

Goal: Find pair adding to 9. Array is sorted. Start pointers at ends.

Custom Input

Target

The visualization matches target using left and right pointers.

Dry Run: nums = [2, 7, 11, 15], target = 9

Iteration	Left (Index/Val)	Right (Index/Val)	Sum (L+R)	Comparison	Action
1	0 / 2	3 / 15	17	17 > 9 (Too Big)	Decrement Right
2	0 / 2	2 / 11	13	13 > 9 (Too Big)	Decrement Right
3	0 / 2	1 / 7	9	9 == 9 (Match!)	Return `[1, 2]`

Edge Cases & Common Mistakes

Edge Cases:

No Solution: Ensure your code handles cases where no pair sums to the target (return empty vector/array).
Array Constraints: Typically length >= 2.

Common Mistakes:

0-based vs 1-based: The problem asks for 1-based indices. Returning [left, right] instead of [left+1, right+1] is a frequent bug!
Not using Sorted Property: Using a Hash Map (O(n) space) works but is explicitly suboptimal when O(1) space is required.

Solution

1def twoSum(numbers: List[int], target: int) -> List[int]:
2    left = 0
3    right = len(numbers) - 1
4    
5    while left < right:
6        current_sum = numbers[left] + numbers[right]
7        
8        if current_sum == target:
9            return [left + 1, right + 1]
10        elif current_sum < target:
11            left += 1
12        else:
13            right -= 1
14            
15    return []

Complexity Analysis

Time Complexity: O(n). We visit each element at most once.
Space Complexity: O(1). We only use two integer variables.

Next Problem

Container With Most Water