167. Two Sum II - Input Array Is Sorted

Medium

Problem:

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].

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

What to learn:

Slicing

Slicing always creates and assigns a new object, so it takes a considerable amount of time to create a new object with slicing. Therefore, for very large arrays, you should be cautious as slicing can take a significant amount of time in processes like copying the entire array or calculating its length.

>>> a = [x for x in range(100000000)]
>>> id(a)
4376898632
>>> b = a
>>> id(b)
4376898632

>>> c= a[:]
>>> id(b)
4377566600

Solution:

Two Pointers

Time complexity: $O(n)$

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1

        while not left == right:
            if numbers[left] + numbers[right] < target:
                left += 1
            elif numbers[left] + numbers[right] > target:
                right -= 1        
            else:
                return left + 1, right + 1

Binary Search

We can check if the rest of the values are correct based on the current value.

Time complexity: $O(nlogn)$

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for k, v in enumerate(numbers):
            left, right = k + 1, len(numbers) - 1
            expected = target - v

            while left <= right:
                mid = left + (right - left) // 2
                if numbers[mid] < expected:
                    left = mid + 1
                elif numbers[mid] > expected:
                    right = mid - 1
                else:
                    return k + 1, mid + 1

bisect Module without Slicing

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for k, v in enumerate(numbers):
            expected = target - v
            i = bisect.bisect_left(numbers, expected, k + 1)
            if i < len(numbers) and numbers[i] == expected:
                return k + 1, i + 1