Problem

Given a sorted array of integers numbers (sorted in non-decreasing order), return the 1-indexed positions of two numbers whose sum equals the given target.

Rules:

  • Each input has exactly one solution.
  • You cannot use the same element twice.
  • Your solution should use O(1) extra space.

Example

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

Output:
[1,2]

Because:

1 + 2 = 3

Since the array is 1-indexed, we return [1,2].

Solution 1: Brute Force

The most straightforward approach is to check every possible pair.

For each element, compare it with every element that comes after it.

If their sum equals the target, return their indices.

Code

from typing import List

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            for j in range(i + 1, len(numbers)):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]

Dry Run

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

Check pairs:

(1,2) → 3 ✅

Return:

[1,2]

Complexity Analysis

Time Complexity

The outer loop runs n times.

For each element, the inner loop may scan the remaining elements.

O(n²)

Space Complexity

We only use a few variables.

O(1)

Although this works, we’re ignoring one important detail…

The array is already sorted.

That allows us to build a much faster solution.

Solution 2: Two Pointers (Optimal)

Since the array is sorted, we don’t need to check every pair.

Instead:

  • Start one pointer at the beginning.
  • Start another pointer at the end.

At every step:

  • Calculate the current sum.
  • If the sum is too small, move the left pointer to the right.
  • If the sum is too large, move the right pointer to the left.
  • If the sum equals the target, we’re done.

Because the array is sorted, moving pointers in this way always moves us closer to the answer.

Why Does This Work?

Suppose:

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

Start:

L            R
1 2 3 4 6

Current sum:

1 + 6 = 7

Found the answer immediately.

Now consider:

numbers = [1,2,3,4,5]
target = 8

Start:

L          R
1 2 3 4 5

Current sum:

1 + 5 = 6

The sum is too small.

Since the array is sorted:

  • Every number to the left of 1 doesn’t exist.
  • The only way to increase the sum is to move the left pointer right.

Now:

  L        R
1 2 3 4 5

Current sum:

2 + 5 = 7

Still too small.

Move left again.

    L      R
1 2 3 4 5

Current sum:

3 + 5 = 8

Found it!

Similarly, if the sum is too large, we move the right pointer left to decrease the sum.

Algorithm

  1. Initialize two pointers:
    • left = 0
    • right = len(numbers) - 1
  2. While left < right:
    • Compute the current sum.
    • If the sum is less than the target, move left.
    • If the sum is greater than the target, move right.
    • Otherwise, return the 1-indexed positions.

Code

from typing import List

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1

        while l < r:
            current = numbers[l] + numbers[r]

            if current < target:
                l += 1
            elif current > target:
                r -= 1
            else:
                return [l + 1, r + 1]

Note: Using elif and else makes the logic clearer because only one condition can be true in each iteration.

Dry Run

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

Start:

L     R
2 3 4

Current sum:

2 + 4 = 6

Target found.

Return:

[1,3]

Another example:

numbers = [1,2,4,6,10]
target = 8

Step 1:

1 + 10 = 11

Too large.

Move right.

1 + 6 = 7

Too small.

Move left.

2 + 6 = 8

Found the answer.

Return:

[2,4]

Complexity Analysis

Time Complexity

Each pointer moves at most n times.

O(n)

Space Complexity

Only two pointers and one variable are used.

O(1)

This satisfies the problem’s requirement of constant extra space.

Brute Force vs Two Pointers

Approach

Time

Space

Brute Force

O(n²)

O(1)

Two Pointers

O(n)

O(1)

The two-pointer solution is significantly faster because it takes advantage of the array already being sorted.

Key Takeaways

  • Always pay attention to the constraints and properties of the input.
  • A sorted array often hints at using the two-pointer technique.
  • Instead of checking every possible pair, eliminate impossible candidates by moving pointers intelligently.
  • The two-pointer approach reduces the time complexity from O(n²) to O(n) while still using O(1) extra space.