LeetCode 167: Two Sum II - Input Array Is Sorted

Problem Restatement

We are given a 1-indexed integer array numbers.

The array is sorted in non-decreasing order.

We need to find two different numbers whose sum equals target.

Return their indices as:

[index1, index2]

The returned indices must be 1-indexed, and:

1 <= index1 < index2 <= len(numbers)

The problem guarantees exactly one valid answer. We cannot use the same element twice, and the solution must use only constant extra space.

Input and Output

Example function shape:

def twoSum(numbers: list[int], target: int) -> list[int]:
    ...

Examples

Example 1:

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

The pair is:

2 + 7 = 9

Their zero-indexed positions are:

0, 1

But the problem asks for 1-indexed positions.

So the answer is:

[1, 2]

Example 2:

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

The pair is:

2 + 4 = 6

Return:

[1, 3]

Example 3:

numbers = [-1, 0]
target = -1

The pair is:

-1 + 0 = -1

Return:

[1, 2]

First Thought: Brute Force

The simplest solution is to try every pair.

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        n = len(numbers)

        for i in range(n):
            for j in range(i + 1, n):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]

        return []

This is correct because it checks every valid pair.

But it takes O(n^2) time.

The array is sorted, so we can do better.

Key Insight

Because the array is sorted, we can use two pointers.

Start one pointer at the smallest number:

left = 0

Start the other pointer at the largest number:

right = len(numbers) - 1

Now compare:

numbers[left] + numbers[right]

There are three cases.

This works because the array is sorted.

Moving left right increases or keeps the left value.

Moving right left decreases or keeps the right value.

Algorithm

Initialize:

left = 0
right = len(numbers) - 1

While left < right:

1. Compute the sum.
2. If the sum equals target, return [left + 1, right + 1].
3. If the sum is smaller than target, increment left.
4. If the sum is larger than target, decrement right.

The +1 is required because the problem uses 1-indexed positions.

Walkthrough

Use:

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

Start:

left = 0
right = 3

Check:

numbers[left] + numbers[right] = 2 + 15 = 17

17 is too large, so move right left.

Now:

left = 0
right = 2

Check:

2 + 11 = 13

13 is still too large, so move right left again.

Now:

left = 0
right = 1

Check:

2 + 7 = 9

This matches the target.

Return 1-indexed positions:

[1, 2]

Correctness

At each step, the algorithm keeps the valid answer inside the range between left and right.

If the current sum is too small, then pairing numbers[left] with any element at or before right cannot reach the target unless we use a larger left value. Since the array is sorted, every value between left + 1 and right is greater than or equal to numbers[left]. So moving left right is safe.

If the current sum is too large, then pairing numbers[right] with any element at or after left is too large unless we use a smaller right value. Since the array is sorted, every value before right is less than or equal to numbers[right]. So moving right left is safe.

The problem guarantees exactly one solution. Since each move discards only impossible pairs, the algorithm eventually reaches the valid pair and returns its 1-indexed positions.

Complexity

Implementation

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        left = 0
        right = len(numbers) - 1

        while left < right:
            total = numbers[left] + numbers[right]

            if total == target:
                return [left + 1, right + 1]

            if total < target:
                left += 1
            else:
                right -= 1

        return []

Code Explanation

We place one pointer at the beginning and one at the end:

left = 0
right = len(numbers) - 1

The loop continues while the two pointers refer to different elements:

while left < right:

Compute the current sum:

total = numbers[left] + numbers[right]

If it matches the target:

return [left + 1, right + 1]

we return 1-indexed positions.

If the sum is too small:

left += 1

we need a larger number.

If the sum is too large:

right -= 1

we need a smaller number.

The final return exists only for completeness. Valid LeetCode input guarantees a solution.

Testing

def run_tests():
    sol = Solution()

    assert sol.twoSum([2, 7, 11, 15], 9) == [1, 2]
    assert sol.twoSum([2, 3, 4], 6) == [1, 3]
    assert sol.twoSum([-1, 0], -1) == [1, 2]
    assert sol.twoSum([1, 2, 3, 4, 4, 9], 8) == [4, 5]
    assert sol.twoSum([-5, -2, 0, 3, 8], 1) == [2, 4]
    assert sol.twoSum([0, 0, 3, 4], 0) == [1, 2]

    print("all tests passed")

run_tests()