167 Two Sum II
Problem Statement
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. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Approach
Using Two Pointers to traverse while they haven't met. Build sum and check against being equal, greater or smaller, then decide if to return or shift the pointers.
Solution
var twoSum = function (numbers, target) {
let [left, right] = [0, numbers.length - 1];
while (left < right) {
const sum = numbers[left] + numbers[right];
const isTargetSum = sum === target;
const isGreater = sum > target;
const isLesser = sum < target;
if (isTargetSum) {
return [left + 1, right + 1];
}
if (isGreater) {
right--;
}
if (isLesser) {
left++;
}
}
return [-1, -1];
};
Questions
- How can we use the sorted input array to our advantage?
- What checks do I need to do and what happens then?
Compare sum against target - How do you know which pointer to shift?
If sum is smaller increase left, if sum is greater decrease right - What kind of loop do we need to use?
While loop until the pointers meet