Leetcode 167: Two Sum II Sorted Input Array

I’ve been doing Leetcode questions lately, and I thought I would share some insights I’ve gleaned in the process of solving them. Jotting down and structuring my thoughts will hopefully allow me — and you, dear reader — into recognizing some of the patterns and approaches we can use.

For this write-up, let’s take a look at Leetcode’s problem 167: Two Sum II today. For this problem, I will be coding in JavaScript, but the underlying concept should be applicable for all programming languages.

Problem:

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.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

What the question is asking: return an array of two indices for the two numbers adding up to the target. Keep in mind that the input array is 1-index.

First, let’s take some notes on the input of the question: We get an array of integer numbers that is:

• sorted in non-decreasing order (aka ascending order)
• 1-indexed (as compared to the 0-indexed array we might be used to)
• there are EXACTLY TWO NUMBERS summing to the TARGET, with the index of one NUMBER smaller than the index of the other NUMBER

This indicates two things to be aware of. One, when we iterate through the array, we have to remember that we’re starting at 1, not 0. And two, that we can use the sorted quality of the array to our advantage, because we know that one number will inevitably be smaller than the other.

So what do we need to do here? First, just from an initial look, we would need:

1. Two variables to keep track of the two indices for the return: one for the larger index, and one for the smaller index
2. Because the array is sorted, and because we are, in essence, searching for two numbers (index of the first number and index of the second number that sum to the TARGET), we can take a two-pointer approach. (Here is a good explainer of the two pointer approach)

To break down our approach, we need to:

1. Return an array of two indices, remembering that the array is 1-indexed
2. Use a two-pointer method, with one pointer for the larger index, and one for the smaller. The left pointer will start from the beginning of the array, and the right pointer will begin at the end.

So far, our pseudo code looks like this:

let ans = [];
let right = array.length — 1; //end of the array
let left = 0; //beginning of the array
while (left < right) {
  let sum = array[ left] + array[right];
  if (sum === target) return [left +1, right +1]; // remembering that array is 1-indexed
}

One question that popped into my mind is how to move the two pointers? Since the array is sorted, with the elements increasing, we do this:

If the target is bigger than the sum of the two numbers , then we increment the left pointer and increase the smaller number.( Decrementing the right pointer and decreasing the larger number would only make the sum smaller and less likely to match the target).

If the target is smaller than the sum of the two numbers, then we decrement the right pointer and decrease the larger number. (Incrementing the left pointer and increasing the smaller number would make the sum even larger, and will not match the target).

So now our pseudocode looks like this:

let ans = [];
let right = array.length — 1; //end of the array
let left = 0; //beginning of the array
while (left < right) {
  let sum = array[ left] + array[right];
  if (sum === target) return [left +1, right +1]; // remembering that array is 1-indexed
  else if (sum < target) {
    left ++
  }else if (sum > target) {
    right - -
  }
}

My complete code looks like the following:

const findTwoSumTarget = (numbers, target) =>{
  let ans = [];
  let right = array.length -1; // remember it is 1 indexed
  let left = 0;
  while (left < right){
    
    if(array[left] + array[right] === target){
      ans.push(left +1, right +1);
      break;
    }else if(array[left] + array[right] > target ){
      right --;
    
    }else{
      left ++;
    }
  }
return ans;
};

Complexity:

Because we iterate through the array once, it will take 0(n) times, with n being the length of numbers.

And it takes 0(1) extra space.

Hope this helps your coding journey. Please feel free to leave comments or questions!