LeetCode #167 | Two Sum II — Input Array Is Sorted (Python)

Problem Analysis:

1. The input array of numbers is sorted, ascending.
2. Return the indices of elements whose sum equals the target + 1.

Solution(a) Breakdown | O(n) time | O(1) space:

Given a sorted array of numbers, we can assign a variable to the first index in the array, and a second variable to last index in the array. Through taking the sum of the values of both variables(i, j) and looping through the input array, we can easily discover our solution. If the sum of numbers[i] and numbers[j] is greater than the target, then we subtract 1 from j. If the sum of numbers[i] and numbers[j] is less than the target, then we add 1 to i. As we adjust our indices, we will eventually reach our target.

Solution Code(a)

(python)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i, j = 0, len(numbers)-1
        while numbers[i] + numbers[j] != target:
            if numbers[i]+numbers[j] > target:
                j -= 1
            else:
                i += 1
        return [i+1, j+1]

Solution(b) Breakdown | O(n) time | O(n) space:

Another and simpler way to tackle this problem is to track each number and index through the use of a dictionary. As we loop through the sorted array of numbers, we check to see if the current number subtracted from the target is in the dictionary. If this value exists as a key, then we have discovered both indices. If the value does not exist as a key, then we add the number pointing to its corresponding index to the dictionary.

Solution Code(b)

(python)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        dictionary = {}
        for index, number in enumerate(numbers):
            if target - number in dictionary:
                return [dictionary[target - number] + 1, index + 1]
            else:
                dictionary[number] = index