Two Sum II

Difficulty: Easy

Problem

The array numbers is sorted in non-decreasing order. Locate two entries at different positions whose values add up to target, and return their positions as 1-based indices.

Example

Input: numbers = [2, 3, 4, 7, 11], target = 10
Output: [2, 4]
Explanation: 3 + 7 = 10, so return [2, 4] (1-based indices).

Brute-force approach

Check every possible pair and see if their sum equals the target.

Steps

  1. For each i, try every j > i
  2. If numbers[i] + numbers[j] == target, return [i+1, j+1]
  3. If no pair found, return no solution

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Too slow for large arrays
  • Doesn't use the sorted property

Optimal approach

Key insight: Because the array is sorted, moving the pointers changes the sum in a predictable way: moving left to the right always increases (or keeps) the left value, so the sum can only go up; moving right to the left always decreases (or keeps) the right value, so the sum can only go down.

Use Two Pointers to leverage the sorted array and find the answer in one pass.

Steps

  1. Initialize left = 0 and right = n - 1
  2. Compute sum = numbers[left] + numbers[right]
  3. If sum == target, return [left + 1, right + 1]
  4. If sum < target, move left forward
  5. If sum > target, move right backward

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function twoSumII(numbers, target):
    left = 0
    right = length(numbers) - 1

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

        if sum == target:
            return [left + 1, right + 1]
        else if sum < target:
            left += 1
        else:
            right -= 1

    return no solution

Hints

  • This array is sorted. Use that to avoid checking all pairs
  • Use two pointers: one at the start and one at the end
  • If the sum is too small move left forward; if too large move right backward

Complexity questions

What is the time complexity of checking all pairs?

O(n²). There are about n*(n-1)/2 pairs, which is O(n²).

What is the time complexity of the two-pointer solution?

O(n). Each step moves at least one pointer, so at most n moves in total = O(n).

What extra space does the two-pointer solution use?

O(1). We only keep two pointers and a few variables, so extra space is O(1).

Check your understanding of Two Sum II

What is special about the input array in Two Sum II?

It is sorted. The array is sorted in non-decreasing order.

Are the returned indices 0-indexed or 1-indexed?

1-indexed. The problem explicitly asks for 1-indexed indices.

For numbers = [2, 7, 11, 15] and target = 9, what are the 1-indexed result indices?

[1, 2]. numbers[0]=2 and numbers[1]=7 sum to 9. Since the problem uses 1-indexed positions, the answer is [1, 2].

Related problems

Keep practising