LeetCode - Two Sum II - Input Array Is Sorted

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.

Problem statement taken from: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted

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 are sorted in non-decreasing order.
- -1000 <= target <= 1000
- The tests are generated such that there is exactly one solution.

Explanation

Binary Search

The problem is similar to our previous Two Sum problem. Instead of returning the numbers, we need to return their indices that sums up to target.

The input array is sorted, which makes it easy and direct for us to use the binary search concept. Let's check the algorithm directly.

- initialize i = 0, j = numbers.size() - 1
  sum = 0

- loop while i < j
  - sum = numbers[i] + numbers[j]

  - if sum > target
    - decrement: j--
  - else if sum < target
    - increment: i++
  - else
    // when the sum is equal to the target
    - return [i + 1, j + 1]
- while end

- return []

Let's check our algorithm in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i = 0, j = numbers.size() - 1;
        int sum;

        while(i < j) {
            sum = numbers[i] + numbers[j];

            if(sum > target) {
                j--;
            } else if(sum < target) {
                i++;
            } else {
                return { i + 1, j + 1 };
            }
        }

        return {};
    }
};

Golang solution

func twoSum(numbers []int, target int) []int {
    i, j := 0, len(numbers) - 1
    sum := 0

    for i < j {
        sum = numbers[i] + numbers[j]

        if sum > target {
            j--
        } else if sum < target {
            i++
        } else {
            return []int{ i + 1, j + 1 }
        }
    }

    return []int{}
}

Javascript solution

var twoSum = function(numbers, target) {
    let i = 0, j = numbers.length - 1;
    let sum = 0;

    while(i < j) {
        sum = numbers[i] + numbers[j];

        if(sum > target) {
            j--;
        } else if(sum < target) {
            i++;
        } else {
            return [i + 1, j + 1];
        }
    }

    return [];
};

Dry Run

Let's dry-run our algorithm for Example 1.

Input: numbers = [2, 7, 11, 15]
       target = 9

Step 1: set i = 0
            j = numbers.size() - 1
              = 4 - 1
              = 3
            sum = 0

Step 2: loop while i < j
        0 < 3
        true

        sum = numbers[i] + numbers[j]
            = numbers[0] + numbers[3]
            = 2 + 15
            = 17

        if sum > target
           17 > 9
           true

           j--
           j = j - 1
             = 3 - 1
             = 2

Step 3: loop while i < j
        0 < 2
        true

        sum = numbers[i] + numbers[j]
            = numbers[0] + numbers[3]
            = 2 + 11
            = 13

        if sum > target
           13 > 9
           true

           j--
           j = j - 1
             = 2 - 1
             = 1

Step 4: loop while i < j
        0 < 1
        true

        sum = numbers[i] + numbers[j]
            = numbers[0] + numbers[3]
            = 2 + 7
            = 9

        if sum > target
           9 > 9
           false
        else if sum < target
           9 < 9
           false
        else
           return [i + 1, j + 1]
           return [0 + 1, 1 + 1]
           return [1, 2]

We return the answer as [1, 2].