Two Sum II - Input Array Is Sorted

This is a classic problem that asks us to find two numbers in a sorted array that add up to a given target. This problem can be solved using various approaches, each with its own time and space complexity trade-offs.

In this article, we will explore four different methods to solve this problem. We will discuss the advantages and disadvantages of each approach and provide implementation details and examples of how to use them. By the end of this article, you will have a better understanding of how to solve this problem efficiently and effectively.

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.

You may not use the same element twice and your solution must use only constant extra space.

---

Approach 1: Brute Force

The approach is to iterate over all possible pairs of numbers in the input array and check if their sum equals the target.

1. We can use a nested loop to iterate over all possible pairs of numbers in the array.

2. For each pair, we check if their sum equals the target.

3. If we find a pair whose sum equals the target, we return their indices.

4. If we don’t find any such pair, we return an empty array.

// ES6 Arrow Function
const twoSum = (numbers, target) => {
    const n = numbers.length;

    for(let i = 0; i < n; i++) {
        for(let j = i + 1; j < n; j++) {
            if(numbers[i] + numbers[j] === target) {
                return [i+1, j+1];
            }
        }
    }

    return [];
}

Time Complexity: O(N²)

Space Complexity: O(1)

Note: we add 1 to the indices returned since the problem asks for 1-based indices rather than 0-based indices.

Note 2: Since we are finding all possible pairs of numbers in the array, it makes it highly inefficient.

---

Approach 2: Binary Search

The problem says the input array is sorted. Nice, thanks for making my life easier! So, when the array is sorted and we have to search for an element, what do we do?

Obviously, we perform a binary search.

So, in this problem, we can perform a binary search for each element in the array to find a complementary element that adds up to the target.

1. We can fix one element in the array and perform a binary search for the other element that complements it to add up to the target.

2. For each element in the array, we use binary search to find its complement.

3. If we find a complement whose sum equals the target, we return their indices.

4. If we don’t find any such complement, we move on to the next element in the array and repeat the process.

5. If we don’t find any pair whose sum equals the target, we return an empty array.

// ES6 Arrow Function
const twoSum = (numbers, target) => {
    const n = numbers.length;

    for (let i = 0; i < n; i++) {
        let left = i + 1;
        let right = n - 1;

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);

            if (numbers[mid] === target - numbers[i]) {
                return [i + 1, mid + 1];
            } else if (numbers[mid] < target - numbers[i]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return [];
}

Time Complexity: O(N²)

Space Complexity: O(1)

---

Approach 3: Two-Pointers

We can use two pointers, one starting from the beginning of the array and the other starting from the end, and move them towards each other until we find two numbers whose sum equals the target.

1. We initialize two pointers, one at the beginning of the array and the other at the end.

2. We calculate the sum of the elements at the two pointers.

3. If the sum is greater than the target, we move the right pointer to the left by one position.

4. If the sum is less than the target, we move the left pointer to the right by one position.

5. If the sum is equal to the target, we return the indices of the two pointers.

6. We repeat steps 2–5 until we find a pair whose sum equals the target, or exhaust all possibilities.

// ES6 Arrow Function
const twoSum = (numbers, target) => {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        const sum = numbers[left] + numbers[right];

        if (sum === target) {
            return [left + 1, right + 1];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

  return [];
}

Time Complexity: O(N)

Space Complexity: O(1)

---

And just like that, we’ve reached the end of our article. Well, it’s been real, it’s been fun, but it hasn’t been real fun. Just kidding, it’s been a blast!

Until we meet again, keep calm and carry on reading. Or binge-watching Netflix, that works too.

Problem - Leetcode 167