167. Two Sum II - Input Array Is Sorted

In this tutorial we will solve 167. Two Sum II - Input Array Is Sorted from leetcode.

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 167. Two Sum II - Input Array Is Sorted

1. Two Sum

Problem statement

We are given a 1-indexed array of integer numbers. The elements in the array is sorted in non-descending order. We are asked to find two numbers that will add up to the target number.

We have to return the indices of the two numbers such that it satisfies the following condition i <= index1 < index2 <= numbers.length. We are not allowed to use the same element of the input array more than once.

We are also told that the tests are generated in such a way that there is exactly one solution.

We should try to solve this problem by using only constant extra space.

Example from leetcode.

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 * 10^4
-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.

Approach

To solve this problem we will take help of two pointers. The first pointer i will be pointing at the first element of the array. The second pointer j will be pointing at the last element of the array.

In each iteration we will check if the sum of the numbers at index i and j adds up to the target number. If yes, then we will return the indices.

If the added sum is greater than the target number then we will decrement j by 1. If the added sum is smaller than the target number then we will increment i by 1.

We will continue this till i < j.

Let use look at the input numbers = [2,7,11,15], target = 9

target = 9

numbers = [2, 7, 11, 15]
           ^         ^
           i         j

is i < j and numbers[i] + numbers[j] === target ?
  -> 2 + 15 is greater than target 9
  -> decrement j


numbers = [2, 7, 11, 15]
           ^     ^
           i     j

is i < j and numbers[i] + numbers[j] === target ?
  -> 2 + 11 is greater than target 9
  -> decrement j


numbers = [2, 7, 11, 15]
           ^  ^
           i  j

is i < j and numbers[i] + numbers[j] === target ?
  -> 2 + 7 is equal to the target 9
  -> we found our numbers and the indices

Code

JavaScript

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
  let i = 0;
  let j = numbers.length - 1;
  while (i < j) {
    const sum = numbers[i] + numbers[j];
    if (sum === target) return [i+1, j+1];
    if (sum < target) i++;
    else j--;
  }
};

Complexity

Time complexity: O(n)

We are looping through the array size n so the time complexity will be O(n).

Space complexity: O(1)

We are taking help of two pointers which takes constant space so the space complexity will be O(1).