40% off Premium for a limited time
InterviewLegend

Two Sum II - Input Array Is Sorted

Alex Chen20 min readEasy
In this lesson
  • Apply the opposite-direction two pointer pattern
  • Understand why sorted arrays enable intelligent pointer movement
  • Implement a clean O(n) time, O(1) space solution

The hash-map Two Sum you just wrote spends O(n) space to hit O(n) time. Sort the array and take that space away, and something cleaner falls out.

The problem changes two things: the array is now sorted, and your space budget drops to constant. Losing the hash map looks like a downgrade. The sorted order pays you back with interest.

Why Sorted Changes Everything

Sorted order is the whole trick, because it makes every pointer move predictable:

  • Move the left pointer right → sum gets bigger (you add a larger number)
  • Move the right pointer left → sum gets smaller (you add a smaller number)

That predictability is what you get in return for the hash map. Instead of testing every pair, each move lets you rule out a whole batch of them at once.

Mental trigger: When you see "sorted array" + "find pair" + "O(1) space" → think two pointers from opposite ends.

Step 1: Start at the Extremes

Put one pointer on the first element, the smallest value, and one on the last, the largest. Starting wide leaves the most room to adjust in either direction.

Two variables, one anchored at each end:

python
left = 0              # Points to smallest value
right = len(nums) - 1  # Points to largest value

Your sum right now is the smallest value plus the largest. If you need it bigger, push left rightward toward larger values; if you need it smaller, pull right inward toward smaller ones.

Step 2: Compare and Decide

Each pass, add the two values and branch on how that sum compares to the target:

python
current_sum = nums[left] + nums[right]  # Sum of current pair
if current_sum == target:
    return [left + 1, right + 1]  # Found it! (1-indexed)
elif current_sum < target:
    left += 1   # Sum too small, need bigger number
else:
    right -= 1  # Sum too large, need smaller number
Why does this work? Take the case where current_sum < target. We need a bigger sum:

• Move left pointer right → sum increases (we get a bigger left value)
• Move right pointer left → sum decreases (we get a smaller right value)

Only moving left can help us. Moving right would make things worse. The same logic applies in reverse when the sum is too large.

Step 3: Repeat Until Pointers Meet

We keep comparing and moving until either we find the answer or the pointers cross (no solution exists).

Here's the full loop. The while left < right guard halts you the moment the pointers meet, and reaching that point means every viable pair has already been ruled out:

python
while left < right:
    current_sum = nums[left] + nums[right]  # Current pair sum
    
    if current_sum == target:
        return [left + 1, right + 1]  # Found! (1-indexed)
    elif current_sum < target:
        left += 1   # Need bigger sum → move left right
    else:
        right -= 1  # Need smaller sum → move right left
return []  # No solution found

Every iteration either returns the answer or drops one element from the running. A solution is guaranteed to exist, so the pointers close in on it well before they cross.

Why Are We Guaranteed to Find the Answer?

The natural worry is that a pointer jumps clean past the pair you needed. It can't, because you only ever discard an element that CAN'T be in the answer. Moving a pointer is a claim: this value, paired with every remaining option on the other side, fails.

When sum < target and we move left: we just tried pairing nums[left] with the LARGEST available number (nums[right]), and the sum was still too small. Pairing it with any smaller number gives an even smaller sum, so it can't be part of the answer. The same logic applies in reverse when we move right.

The guarantee: Each move eliminates exactly one element that provably can't be in the answer. Since the problem guarantees a solution exists, we will find it before the pointers cross.

Visual Walkthrough

Trace finding two numbers that sum to 9 in [2, 7, 11, 15]:

Initial State
left starts at index 0 (smallest), right at index 3 (largest). Sum = 2 + 15 = 17.
2
7
11
15
0
1
2
3
left
right
target = 9
sum = 17 > 9

Try It Yourself

Start at both ends, compare sum to target, and move the appropriate pointer.

Try it yourself

Two Sum II

Given a 1-indexed array of integers numbers that is 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 (1-indexed) as an array [index1, index2].

Constraints:
• The solution must use only constant extra space
• Each input has exactly one solution
• You may not use the same element twice

Examples

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

Output: [1, 2]

numbers[1] + numbers[2] = 2 + 7 = 9

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

Output: [1, 3]

numbers[1] + numbers[3] = 2 + 4 = 6

Two Sum II

Loading...
Click "Run" to execute your code

Test Cases

Input: [2, 7, 11, 15], 9Expected: [1, 2]
Input: [2, 3, 4], 6Expected: [1, 3]
Input: [-1, 0], -1Expected: [1, 2]
Input: [1, 2, 3, 4, 5], 8Expected: [3, 5]

Solution

def solution(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Time: O(log n) | Space: O(1)

Solution

Take some time to think about the problem before revealing the solution. Try to write the code yourself first - that's where the real learning happens.

Things to Watch Out For

Three things snag people here:

1. 1-indexed output: The problem asks for 1-indexed results! Don't forget to add 1 to your indices before returning.

2. Using a hash map: It works but violates the O(1) space requirement. Two pointers is what buys you constant space here.

3. Using left <= right: Should be left < right. If they're equal, you'd be using the same element twice.

The Opposite Direction Pattern

Two Sum II is opposite-direction two pointers stripped to the bone. Start at both ends, compare, decide which pointer moves. Every harder variant reuses this same move, just applied to a problem that looks different on the surface.

The sorted-array guarantee, knowing exactly which way the sum shifts when you move a pointer, is the piece that carries over into Container With Most Water, 3Sum, and Trapping Rain Water.

Key Takeaways

  • Sorted array + pair search = opposite direction two pointers
  • Sum too small → move left pointer right to increase
  • Sum too large → move right pointer left to decrease
  • The sorted property guarantees you can't miss the answer
Next: Valid Palindrome