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.
Recommended Time and Space Complexity
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)
Binary Search
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)