Two Integer Sum II

Problem Statement

Given an array of integers numbers that is sorted in non-decreasing order.

Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.

There will always be exactly one valid solution.

Your solution must use O(1) additional space.

Example 1:

Input: numbers = [1,2,3,4], target = 3


Output: [1,2]

Explanation: The sum of 1 and 2 is 3. Since we are assuming a 1-indexed array, index1 = 1, index2 = 2. We return [1, 2].

Constraints:

  • 2 <= numbers.length <= 1000
  • -1000 <= numbers[i] <= 1000
  • -1000 <= target <= 1000

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force solution would be to check every pair of numbers in the array. This would be an O(n^2) solution. Can you think of a better way?

Hint 2

Can you think of an algorithm by taking the advantage of the array being sorted?

Hint 3

We can use the two-pointer algorithm. If nums[0] + nums[n-1] > target, then we know nums[n - 1] cannot possibly be included in any pairs. Why? Because nums[n - 1] is the largest element in the array. Even by adding it with nums[0], which is the smallest element, we still exceed the target. You can think of the case when nums[0] + nums[n - 1] < target.

Hint 4

Keep two pointers, one at the start and the other at the end of the array. If the sum of the numbers at the two pointers is greater than the target, decrement the right pointer, else increment the left pointer. Repeat this process until you find a valid pair.

Solution

Brute Force

def two_sum(numbers: List[int], target: int) -> List[int]:
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]
    return []

Time complexity: O(n ^ 2) Space complexity: O(1)

def two_sum(numbers: List[int], target: int) -> List[int]:
    for i in range(len(numbers)):
        left, right = i + 1, len(numbers) - 1
        temp = target - numbers[i]
        while left <= right:
            mid = left + (right - left) // 2
            if numbers[mid] == temp:
                return [i + 1, mid + 1]
            elif numbers[mid] < temp:
                left = mid + 1
            else:
                right = mid - 1
    return []

Time complexity: O(n log n) Space complexity: O(1)

Hash Map

from collections import defaultdict


def two_sum(numbers: List[int], target: int) -> List[int]:
    num_map = defaultdict(int)
    for i in range(len(numbers)):
        temp = target - numbers[i]
        if num_map[temp]:
            return [num_map[temp], i + 1]
        num_map[numbers[i]] = i + 1
    return []

Time complexity: O(n) Space complexity: O(n)

Two Pointers

def two_sum(numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1


    while left < right:
        current_sum = numbers[left] + numbers[right]


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

Time complexity: O(n) Space complexity: O(1)