Two Sum II - Input Array Is Sorted
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.
Return the indices of the two numbers (1-indexed) as an integer array [index1, index2].
You may not use the same element twice.
Your solution must use only constant extra space.
Examples
numbers = [2,7,11,15], target = 9[1,2]numbers = [2,3,4], target = 6[1,3]numbers = [-1,0], target = -1[1,2]Constraints
2 <= numbers.length <= 3 * 10^4-1000 <= numbers[i] <= 1000numbers is sorted in non-decreasing order-1000 <= target <= 1000The tests are generated such that there is exactly one solution
š” Hints
Hint 1
Since the array is sorted, think about what happens when the sum of two elements is too large or too small.
Hint 2
Use two pointers ā one at the start and one at the end. If the sum is too large, move the right pointer left. If too small, move the left pointer right.
Algorithm Complexity
Official asymptotic Big-O runtime and auxiliary memory analysis
Two pointers approach: start from both ends. If sum equals target, return. If sum is too small, move left pointer right to increase sum. If too large, move right pointer left to decrease sum.
Two pointers start at the outer ends and move inward based on whether the current sum is less than or greater than target.
Operates directly on the input array using two integer index pointers with zero auxiliary collections.
š Real-World Use Cases
In Amazon's fulfillment system, finding two packages whose combined weight matches a container's capacity uses the same two-pointer approach on a sorted weight list.
Finding two ad campaigns whose combined cost matches a target budget from a sorted list of campaign prices.
š Dry Run
Initialize left=0 (pointing to 2) and right=3 (pointing to 15)