Two Sum II Input Array Is Sorted
(#167), Medium
Category: Array, Two Pointer, Binary Search
Problem Statement
You're given a 1-indexed array of integers called numbers, sorted in non-decreasing order. Your task is to find two numbers such that they add up to a given target. Return their indices (1-based) as an array [index1, index2], where 1 <= index1 < index2 <= numbers.length. ⚠️ Each input has exactly one solution, and you cannot use the same element twice. 🧠 Also, your solution must use only constant extra space.
Examples
Input: numbers = [2, 8, 11, 13, 15, 16, 25], target = 28
Output: [2, 6]
Explanation: 8 (at index 2) + 20 (at index 6) = 28
Approach
Approach: Two Pointer
- Initialize two pointers: `start = 0` and `end = numbers.length - 1`.
- While `start < end`, calculate the sum of numbers[start] + numbers[end].
- If the sum equals the target, return `[start + 1, end + 1]` (1-based indexing).
- If the sum is less than target, increment `start` to increase the sum.
- If the sum is greater than target, decrement `end` to decrease the sum.
- Repeat the process until a valid pair is found.
var twoSum = function(numbers, target) {
let start = 0;
let end = numbers.length - 1;
while (start < end) {
let sum = numbers[start] + numbers[end];
if (sum === target) {
return [start + 1, end + 1];
}
if (sum < target) {
start++;
} else {
end--;
}
}
};Complexity
Time: O(n), where n is the number of elements in the array.
Space: O(1), since no extra space is used.