Two Sum II - Input Array Is Sorted

Similar to 2-sum, but input array is sorted in ascending order.

Brute Force

Apparently it’s an $O (n^{2})$ algorithm.

l = len(numbers)
for i in range(l):
    for j in range(l):
        if i != j and numbers[i] + numbers[j] == target:
            return [i + 1, j + 1]

A slightly improved brute force algorithm that eliminates roughly half of the combinations — asymptotic complexity is the same.

l = len(numbers)
i, j = 0, 1
while i < l - 1:
    while j < l:
        if numbers[i] + numbers[j] == target:
            return [i + 1, j + 1]
        j += 1
    i += 1
    j = i + 1

Two Point

This algorithm runs in $O (n)$ since we’re approaching the target from both ends of the array.

i, j = 0, len(numbers) - 1
while i < j:
    s = numbers[i] + numbers[j]
    if s == target:
        return [i + 1, j + 1]
    elif s > target:
        j -= 1
    else:
        i += 1