167.two-sum-ii-input-array-is-sorted.md

167. Two Sum II - Input Array Is Sorted

Two Pointers

Since the array is sorted, if we put two pointers at the leftmost and rightmost position to sum up, then:

• As we move from left to right, the sum increases.
• As we move from right to left, the sum decrease.

[smallest, ..., largest]
 L -->            <-- R

We calculate the sum of left and right pointer, compare to target, and then decide which pointer to move until the two pointer meets.

• The sum is too small sum < target, then move L to increase the sum.
• The sum is too large sum > target, then move R to decrease the sum.

target = 9
[2, 3, 4, 6, 8]
 L           R
 2 +         8 = 10 > 9
    3 +      8 = 11 > 9
       4 +   8 = 12 > 9
           ... skip

In the beginning A[L] + A[R] = 2 + 8 = 10 > 9, that means that all numbers after L sum with A[R] will be also larger than 9 (sorted), so we need to discard A[R] by moving R.

def twoSum(self, numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        sum = numbers[left] + numbers[right]
        if sum == target:
            # 1-based index
            return [left + 1, right + 1]
        elif sum < target:
            left += 1
        else:
            right -= 1
    return None

fun twoSum(numbers: IntArray, target: Int): IntArray {
    var left = 0
    var right = numbers.size - 1
    while (left < right) {
        val sum = numbers[left] + numbers[right]
        if (sum == target) return intArrayOf(left + 1, right + 1)
        else if (sum < target) left++
        else right--
    }
    // Dummy return
    return intArrayOf(0, 0)
}

• Time Complexity: O(n).
• Space Complexity: O(1).

Hash Table

Same to 1. Two Sum but not optimal solution since we don't use the characteristic: input array is sorted.

Binary Search

We iterate the first number and use binary search for remaining number. Here are some points to note:

1. We iterate until the second last number.
2. We search starting from the next number of current number, because the array is sorted, and we don't want to search the same number.

fun twoSum(numbers: IntArray, target: Int): IntArray {
    // We iterate until the second last number
    for (i in 0 until numbers.size - 1) {
        val current = numbers[i]
        // We search starting from the next number of current number
        val searchIndex = binarySearch(numbers, target - current, i + 1)
        if (searchIndex != -1) return intArrayOf(i + 1, searchIndex + 1)
    }
    return intArrayOf(-1, -1)
}

private fun binarySearch(nums: IntArray, target: Int, start: Int): Int {
    var left = start
    var right = nums.size - 1
    while (left <= right) {
        var middle = left + (right - left) / 2
        if (nums[middle] == target) return middle
        if (nums[middle] < target) left = middle + 1
        else right = middle - 1
    }
    return -1
}

• Time Complexity: O(n log n).
• Space Complexity: O(1).