LeetEye LeetEye
Easy Two Pointers ~5 min

Two Sum II - Input Array Is Sorted

two-pointers 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 (1-indexed) as an integer array [index1, index2].

You may not use the same element twice. There is exactly one solution.

Constraint: Must use only constant extra space.

Examples

Example 1
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
2 + 7 = 9. Index1 = 1, Index2 = 2.
Example 2
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Example 3
Input: numbers = [-1,0], target = -1
Output: [1,2]
Key Insight

In a sorted array, the sum of two elements tells you how to adjust.

In sorted arrays, two pointers from ends let you search in O(n) time, O(1) space — sum too small means move left pointer right, too big means move right pointer left.

How to Approach This Problem

Pattern Recognition: When you see keywords like two sum ii - input array is sorted two-pointers, think Two Pointers.

Step-by-Step Reasoning

1 The problem requires O(1) space. Why does hash map violate this?
Answer: Hash maps use O(n) space
Hash map stores up to n elements. The problem explicitly requires constant space.
2 Because the array is sorted, if nums[L] + nums[R] < target, we know:
Answer: We need a larger sum, so move L right
Moving L right gives us a larger number on the left, increasing the sum. Moving R left would decrease sum further — wrong direction.
3 If nums[L] + nums[R] > target, we should:
Answer: Move R left (decrease sum)
Sum too big → need smaller numbers → only way is to move R left (can't move L left, it's already as far left as possible relative to our search).
4 Why are we guaranteed to find the answer (if it exists) with this approach?
Answer: Each move eliminates impossible candidates while preserving the answer
When we move L right (sum too small), we eliminate all pairs with current L because they'd all be too small. Answer is preserved because it needs a larger left value. Similarly for moving R.
5 The loop terminates when:
Answer: Either A or B
Either we find it and return, or pointers cross (which shouldn't happen given "exactly one solution" guarantee, but is the logical stopping point).

Solution

def twoSum(numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif current_sum < target:
            left += 1  # Need larger sum
        else:
            right -= 1  # Need smaller sum
    
    return []  # No solution found

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Two Pointers problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye