[LeetCode] #167

In this article, we are going to look at how to solve the LeetCode Question 167, 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[index<sub>1</sub>] and numbers[index<sub>2</sub>] where 1 <= index<sub>1</sub> < index<sub>2</sub> <= numbers.length.

Return the indices of the two numbers, index<sub>1</sub> and index<sub>2</sub>, added by one as an integer array [index<sub>1</sub>, index<sub>2</sub>] 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].

Approach

Looking at the examples given by LeetCode, we can see that we can use two pointers for this problem since the array is sorted.

If we have two pointers named, left and right with initial indexes 0 and n -1. Here, n is the length of the array numbers(n = numbers.length). Then we can calculate the sum which is numbers[left] + numbers[right] . If the sum is greater than the target value we can decrease the right index. And if the sum is lower than the target value we can increase the left index. And when we get an answer that satisfies the condition sum == target we can get the right and left indices and return them as an array.

When the right index is less than left index, we know that there isn’t a combination that satisfies the condition sum == target. In that case, we return an array consisting {-1, -1}.

Solution

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        int left = 0, right = n - 1;
        while(left < right){
            int sum = numbers[left] + numbers[right];
            if(sum < target){
                left++;
            } else if(sum > target){
                right--;
            } else{
                return new int[]{left + 1, right + 1};
            }
        }
        return new int[] {-1,-1};
    }
}

Since we are not using any additional spaces in memory for this solution, the space complexity of this algorithm is O(1).

The time complexity of this algorithm is, O(n) because in the worst-case scenario, the algorithm runs until the left pointer is equal to right pointer going through n elements in n iterations.