NeetCode 150: Two Sum II - Input Array Is Sorted

Published: at 08:06 PM

Table of contents

Open Table of contents

The 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 1Example 2Example 3
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].		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].		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].

The Approach

The goal is to get the pair of indexes in place. Since the array is sorted, we can leverage its ordering to find the pair.

The array is ordered in an increasing order (non-decreasing). As such, moving up the array would increase the value, & moving down would decrease the value. We use two pointers, left & right, which start at each end of the array, calculating the current sum of the pair.

If the current sum is greater than target, decrease the value by moving the right pointer backwards (cannot move the left pointer due to edge case of starting at 0). If the current sum is smaller than target, increase the value by moving the left pointer fowards.

My Solution

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] answer = new int[2];
        int l = 0;
        int r = numbers.length - 1;

        // Until the two pointers cross, get the currentSum.
        // This is because numbers is already sorted in an increasing order,
        // so moving up the array would increase currentSum & vice versa.
        while (l < r) {
            int currentSum = numbers[l] + numbers[r];

            // currentSum == target: Add the two indexes to answer & return.
            if (currentSum == target) {
                answer[0] = l + 1;
                answer[1] = r + 1;
                return answer;

            // currentSum > target: Shift r behind to decrease currentSum.
            } else if (currentSum > target) {
                r--;

            // currentSum < target: Shift l forward to increase currentSum.
            } else {
                l++;
            }
        }
        return answer;
    }
}

Firstly we initialize the left & right pointers. l & r respectively, along with the answer array.

Until the left pointer, l, crosses the right pointer, r (all pairs have been considered), continue to calculate the currentSum. Based on comparing currentSum to target, there are 3 scenarios:

answer is then returned.