167.Two_Sum_II_(Medium).md

167. Two Sum II - Input Array Is Sorted (Medium)

Date and Time: Jun 2, 2024, 4:34 AM (EST)

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

Question:

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

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

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

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

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

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

Two Pointers Solution:

Use two pointers and only consider three cases (since numbers is sorted in non-decreasing order): 1: if numbers[l] + numbers[r] < target, we increment l because the number on the left is lower than its right. 2. if numbers[l] + numbers[r] > target, we decrement r because the number of the right is greater than its left. 3. if numbers[l] + numbers[r] == target, return [l+1, r+1].

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers)-1
        while l < r:
            if numbers[l] + numbers[r] < target:
                l += 1
            elif numbers[l] + numbers[r] > target:
                r -= 1
            else:
                return [l+1, r+1]

Time Complexity: $O(n)$
Space Complexity: $O(1)$

Python Hashmap Solution:

We loop over numbers, and each time we save the {diff: index} into hashmap{}, where diff = target - numbers[i], then we check if numbers[i] in hashmap, then we return [hashmap[numbers[i]+1], i + 1].

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # hashmap = {7: 0, 2, 1}
        hashmap = {}
        for i in range(len(numbers)):
            if numbers[i] in hashmap:
                return [hashmap[numbers[i]]+1, i+1]
            hashmap[target-numbers[i]] = i

Time Complexity: $O(n)$
Space Complexity: $O(n)$