Algorithm

Two Sum II - Input Array Is Sorted

Two Pointer Pattern

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.

CONSTRAINTS
  • 2 <= numbers.length <= 3 × 10^4
  • Array is sorted in non-decreasing order
  • Exactly one solution exists
  • Must use O(1) extra space
EXAMPLE 1
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
2 + 7 = 9, and those sit in the 1st and 2nd positions.
EXAMPLE 2
Input: numbers = [2,3,4], target = 6
Output: [1,3]
2 + 4 = 6. The 3 in the middle is not needed.
EXAMPLE 3
Input: numbers = [-3,-1,0,2,5], target = -1
Output: [2,3]
-1 + 0 = -1. Negative numbers still obey the sorted order, so the same reasoning applies.
Are the returned positions 0-based or 1-based?
1-based. The two smallest valid positions are 1 and 2, not 0 and 1.
Is a solution always guaranteed?
Yes — exactly one pair adds up to the target, so you never have to handle a 'not found' case.
Can the same element be used twice?
No. The two positions must be different, which the left < right condition enforces automatically.
Can the array contain duplicates or negative numbers?
Yes to both. It is non-decreasing (duplicates allowed) and values may be negative; the sorted-order argument holds regardless.

When we have a sorted dataset, we have a massive advantage: information about one element tells us exactly where to look for others. Instead of guessing, we can make informed decisions based on the current sum.

Checking Every Possible Pair (O(N²))

The most basic approach is to pick every possible first number and then scan the rest of the array to see if its partner exists. This approach completely ignores the fact that the array is sorted. It is highly inefficient because it re-scans the same numbers over and over, leading to quadratic time complexity.

python
# Brute force: nested loops
def brute_force(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i + 1, j + 1]
Why Binary Search is a Partial Step Forward

Since the array is sorted, we could improve our search. For every number nums[i], we could perform a binary search to find target - nums[i] in the remaining part of the array. While this improves time complexity to O(N log N), it still feels clunky because we are performing a search from scratch for every single element, ignoring the relationship between adjacent numbers.

The Two-Pointer Insight

Because the array is sorted, the data has a "directional bias"—smaller values are on the left, and larger values are on the right. This allows us to use two pointers to "squeeze" the search space from both ends, effectively turning a multi-step search into a single, O(N) pass. We place one pointer at the start (Left) and one at the end (Right), acting as a pressure valve to adjust our sum toward the target.

Converging on the Solution

- If the current sum is too small, we need a larger value. Moving the Left pointer to the right increases the sum.
- If the current sum is too large, we need a smaller value. Moving the Right pointer to the left decreases the sum.
This approach is optimal because every movement eliminates exactly one value that we now know cannot be part of the solution.

python
# Optimal: two pointers
def two_pointers(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
Worked Example:[2, 7, 11, 15], target = 9
0
2
L
1
7
2
11
3
15
R
We place Left at index 0 (2) and Right at index 3 (15). The current sum is 2 + 15 = 17 (too large).
0
2
L
1
7
2
11
R
3
15
Since 17 > 9, we move the Right pointer left to index 2. The current sum is 2 + 11 = 13 (still too large).
0
2
L
1
7
R
2
11
3
15
Since 13 > 9, we move the Right pointer left to index 1. The sum is 2 + 7 = 9, which matches our target!
Interactive Strategy Visualization

Two Sum II Visualization

Converging pointers on a sorted array

LEFT
2
7
11
RIGHT
15
Left Value
2
+
Right Value
15
=
Current Sum
17
TARGET
9

Crucial Concept

  • Monotonic Sum: Moving 'Left' right increases sum. Moving 'Right' left decreases sum.
  • Deterministic: At any step, we know exactly which pointer to move based on the sum comparison.
  • No Backtracking: Pointers only move in one direction (inward), guaranteeing O(N).
LOGICSTEP 1/4
The search begins! We place our pointers at the very ends of our sorted collection: 2 and 15. Together, they sum to 17—way too large for our target of 9!
Decision: Move ← Right
TIP

Pattern Recognition

Whenever you need to find a pair in a sorted array, always consider the Two Pointer approach. It almost always beats the O(N) hash map approach in space complexity (O(1) vs O(N)).

O(N²) Brute Force
→
O(N log N) Binary Search Per Element
→
O(N) Time · O(1) Space Converging Scan