Two Sum II - Input Array Is Sorted

Problem statement

Find two numbers in a sorted non-decreasing order 1-indexed array that adds up to the target. Return their indices (1-indexed) as [index1, index2] in an integer array of length 2. The solution should use constant extra space.

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.

Examples

a = [2, 7, 11, 15], target = 9

output = [1, 2]

Sudo Code

1. Initialize the variables

2. Loop till left and right cross each other

   1. If we get an answer exit

   2. If the sum of left and right is less than the target then increase the sum by incrementing the left pointer.

   3. If the sum is greater than the target, then decrease the sum by decrementing the right pointer

Note - You can use binary search also, but the time complexity will increase to log(nlogn)

Dry Run

Solution

// Two pointers
    public int[] twoSum(int[] numbers, int target) {
        // 1. Initialize the variables
        int n = numbers.length;
        int left = 0, right =  n-1;

        // 2. Loop till left and right cross each other
        while(left <= right){
            int sum = numbers[left] + numbers[right];

            if(target == sum){
            // 2.1 If we get anwer exit
                break;
            }else if(sum < target){
            // 2.2 If sum of left and right is less than target then increase the sum by incrementing left pointer.
                left++;
            }else{
            // If sum is greater than target, then decrese the sum by decrementing right pointer
                right--;
            }
        }
        return new int[]{left+1, right+1};
    }

Time complexity Analysis

Time Complexity - O(N)

Space Complexity - O(1)

Topics Covered

Two Pointer

Companies

Amazon, Facebook, Google