Two Sum II - Input Array Is Sorted(#167)
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]
🧠 Approach
We use the Two Pointer approach since the array is sorted:
• Initialize two pointers: one at the beginning (`start = 0`) and one at the end (`end = numbers.length - 1`).
• Compute the sum of the numbers at these pointers.
• If the sum equals the target, return [start + 1, end + 1].
• If the sum is less than the target, move the start pointer forward.
• If the sum is greater than the target, move the end pointer backward.
This works in O(n) time and O(1) space.
💻 Code
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.