Medium

Two Sum II - Input Array Is Sorted

034

Given a 1-indexed sorted array, return the two indices whose values add up to target.

EXAMPLES

Example 1

Input
{
  "numbers": [
    2,
    7,
    11,
    15
  ],
  "target": 9
}

Output
[
  1,
  2
]

FUNCTION SHAPE

numbers: intArraytarget: int→intArray

SOLUTION NOTE

Why does this work?

If A[i] + A[j] is too big (> T), we must decrement j to reduce the sum, because incrementing i will increase the sum (A is sorted).

Similarly, if A[i] + A[j] is too small (< T), we must increment i to increase the sum, because decrementing j will decrease the sum.

When we move i forward with A[i] + A[j] < T, all pairs (i, k) for k: i < k < j have sum clearly even smaller than A[i] + A[j] < T, since A[k] < A[j], so we can safely discard them.

Reveal reference solution +

pythonREFERENCE

def twoSum(self, A: List[int], T: int) -> List[int]:
    i, j = 0, len(A) - 1
    while i < j:
        if A[i] + A[j] == T:
            return [i + 1, j + 1]
        elif A[i] + A[j] > T:
            j -= 1
        else:
            i += 1
    return [-1, -1]

TimeO(n)

SpaceO(1)

Open on LeetCode ↗