Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input array is already sorted in non-decreasing order, and the goal is to find the two numbers whose sum equals the target.

The detail that matters most is not the sum itself. It is the sorted order.

If the array were unsorted, the usual idea would be a hash map. But once the numbers are sorted, the problem becomes easier to reason about from both ends at the same time.

The return value is also slightly unusual: the answer must be the two indices in 1-based form, not 0-based form.

Why the sorted order changes everything

Suppose two pointers are placed at the ends of the array:

  • left starts at the smallest number
  • right starts at the largest number

Now compare numbers[left] + numbers[right] with the target.

If the sum is too small, moving the right pointer left would only make the sum smaller or keep it the same, which cannot help. The only sensible move is to increase the smaller value by moving left to the right.

If the sum is too large, moving the left pointer right would only make the sum larger or keep it the same. The only sensible move is to decrease the larger value by moving right to the left.

That is the whole trick. The sorted order makes one pointer movement obviously correct at every step.

How to derive the optimal solution

A brute-force approach checks every pair. That works, but it takes O(n^2) time, which wastes the fact that the array is sorted.

The next reasonable idea is: for each index, binary search for target - numbers[i]. That uses the sorted property and runs in O(n log n).

But the sorted array gives even more structure than that. When the candidate pair is too small, the smaller number must go up. When the candidate pair is too large, the larger number must go down. There is no need to restart a search for each element.

That leads directly to the two-pointer method:

  1. Start with the widest possible pair.
  2. Compute the sum.
  3. If the sum is too small, move left right.
  4. If the sum is too large, move right left.
  5. If the sum matches, return the indices.

Each pointer only moves in one direction, so the whole scan is linear.

Best approaches

The per-element binary-search solution is a valid intermediate answer:

  • Time: O(n log n)
  • Extra space: O(1)
  • Strength: easy to explain if the interviewer first asks for a solution that uses the sorted property

The two-pointer solution is the optimal default:

  • Time: O(n)
  • Extra space: O(1)
  • Strength: fully exploits the sorted array and stays very simple

Python solution

from typing import List, Sequence


def find_two_sum_indices(sorted_numbers: Sequence[int], target_sum: int) -> List[int]:
    """
    Return the 1-based indices of the two numbers whose sum equals target_sum.

    The input is assumed to be sorted in non-decreasing order, which allows
    a linear-time two-pointer scan.
    """
    left_index = 0
    right_index = len(sorted_numbers) - 1

    while left_index < right_index:
        left_value = sorted_numbers[left_index]
        right_value = sorted_numbers[right_index]
        current_sum = left_value + right_value

        if current_sum == target_sum:
            # LeetCode expects 1-based indices.
            return [left_index + 1, right_index + 1]

        # If the sum is too small, the only useful move is to increase it.
        if current_sum < target_sum:
            left_index += 1
            continue

        # If the sum is too large, the only useful move is to decrease it.
        right_index -= 1

    # The original problem guarantees exactly one valid answer, but this keeps
    # the helper safe if it is reused in a different context.
    raise ValueError("No pair of values sums to the requested target.")


class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        return find_two_sum_indices(sorted_numbers=numbers, target_sum=target)

Why this works

The correctness comes from eliminating impossible pairs without ever discarding the real answer.

If numbers[left] + numbers[right] is smaller than the target, then pairing numbers[left] with any index between left and right still cannot reach the target, because every number in that range is at most numbers[right]. So left cannot belong to the answer, and moving it right is safe.

If numbers[left] + numbers[right] is larger than the target, then pairing numbers[right] with any index between left and right still cannot hit the target, because every number in that range is at least numbers[left]. So right cannot belong to the answer, and moving it left is safe.

Because each step removes at least one impossible endpoint and both pointers move only inward, the algorithm eventually reaches the unique valid pair.

With n elements, each pointer moves at most n - 1 times, so the running time is O(n). The algorithm stores only a few variables, so the extra space is O(1).

Interview follow-ups

What if the array were not sorted?

Then the cleanest optimal solution is usually a hash map. Scan from left to right, and for each value x, check whether target - x has already been seen. If it has, the pair is found. Otherwise store x and its index. That runs in O(n) time with O(n) extra space.

The contrast is useful in interviews: unsorted input favors a hash map, while sorted input favors two pointers because the ordering lets each pointer movement rule out many candidates at once.

Could binary search still be used here?

Yes. For each index i, binary search the suffix for target - numbers[i]. That works because the array is sorted, and it uses only O(1) extra space. The tradeoff is time: it takes O(n log n) instead of O(n).

This is a good follow-up because it shows a reasonable step between brute force and the optimal answer. It also helps explain why the two-pointer solution is better: it avoids repeating a fresh search for every element.

Why is it safe to move only one pointer at a time?

Because the sorted order makes the direction forced by the comparison.

If the sum is too small, decreasing the right endpoint cannot help, since that only keeps the right value the same or makes it smaller. The only possible improvement is to increase the left value.

If the sum is too large, increasing the left endpoint cannot help, since that only keeps the left value the same or makes it larger. The only possible improvement is to decrease the right value.

That one-way logic is exactly why the method is both correct and linear.

What changes if the problem asks for all unique pairs instead of exactly one pair?

The two-pointer pattern still works, but after finding one valid pair, both pointers should move inward and skip duplicates so the same value pair is not reported multiple times.

That version turns into the same duplicate-handling idea used in problems like 3Sum: sorted input makes it easy to group equal values together and avoid repeated answers without extra hash sets.

What if the interviewer asks for the proof in one sentence?

The proof is that when the current sum is too small, every pair using the current left value is also too small, so that left value can be discarded; and when the current sum is too large, every pair using the current right value is also too large, so that right value can be discarded.

Once that elimination argument is clear, the rest of the algorithm is just repeating the same safe step until the correct pair is reached.

Practical takeaway

This problem is a good reminder that the right data property can be more important than the right data structure.

The sorted order is the real asset. Once that is recognized, the solution becomes a simple inward scan that is both faster and easier to explain than the usual hash-map approach.