167 Two Sum II - Input Array is Sorted

1. Description

Given a 1-indexed array of integers numers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target. Let these two numbers be numbers[index1] and numbers[index2] where \(1 \leq index1 \leq index2 \leq numbers.length\).

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

Constraints:

1. The tests are generated such that there's exactly one solution. You may not use the same element twice.
2. \(2 \leq numbers.length \leq 3*10^{4}\)
3. \(-1000 \leq numbers[i] \leq 1000\)
4. \(numbers\) is sorted in non-decreasing order
5. \(-1000 \leq target \leq 1000\)

1.1. Examples:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

2. Solution

2.1. Understanding the problem

A naive approach would be just start from the left and add each element with the rest of the elements that have not been added to the current element before. This would take \(O(N^{2})\) time.

However, if we consider the fact that this is a sorted array, we can start from both ends and exclude a significant amount of pairs. In fact this will cut the time down to \(O(N)\).

2.2. Algorithm

1. We start from left_idx = 0 and right_idx = len(numbers) - 1.
2. if numbers[left_idx] + numbers[right_idx] == target, we add 1 and return the two indices.
   1. if numbers[left_idx] + numbers[right_idx] < target, then left_idx += 1
   2. if numbers[left_idx] + numbers[right_idx] > target , then right_idx -= 1
3. go back to 2.

2.3. Code

Listing 1: 167 Two Sum II - Input Array is Sorted my solution

def twoSum(numbers, target):
    """
    :type numbers: List[int]
    :type target: int
    :rtype: List[int]
    """
    left_idx = 0
    right_idx = len(numbers) - 1

    # could've used while True but just make sure loop will always terminate
    while left_idx <= right_idx:
        if (numbers[left_idx] + numbers[right_idx]) == target:
            return [left_idx+1, right_idx + 1]
        elif numbers[left_idx] + numbers[right_idx] < target:
            left_idx += 1
        elif numbers[left_idx] + numbers[right_idx] > target:
            right_idx -= 1


# tests
numbers = [2,7,11,15]
target = 9
output = [1, 2]
print(twoSum(numbers, target) == output)


numbers, target = [2, 3, 4],  6
output = [1, 3]
print(twoSum(numbers, target) == output)

numbers, target = [-1, 0],  -1
output = [1, 2]
print(twoSum(numbers, target) == output)

Listing 2: 167 Two Sum II - Input Array is Sorted my solution-results

True

2.3.1. Complexity

2.3.1.1. Time complexity:

O(N) because we only traverse the array once.

2.3.1.2. Space complexity:

O(1).

2.4. Leetcode solution

Same.

Listing 3: 167 Two Sum II - Input Array is Sorted leetcode solution

<<imports for typing>>

Listing 4: 167 Two Sum II - Input Array is Sorted leetcode solution-results

2.4.1. Time complexity:

2.4.2. Space complexity:

3. More analysis

3.1. General thoughts

The whole solution is based on the following fact:

1. The array is sorted.

3.2. Related problems

4. Log time