Two sum

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.

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

Step 1 : – Template Implementation

There are two types of two pointer templates.

1). Opposite direction two pointer template

2). Same direction two pointer template

Based on our analysis of the Two Sum problem statement, we need to handle all three scenarios of the problem. Therefore, there’s no need to modify our template, and we can use the same opposite-direction two-pointer approach.

Java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
       int left = 0;
       int right = numbers.length - 1;
        
        while (left < right) {
        //code

            if (param1 == target) {
            // code 
        
                left++;
                right--;
            } else if (param1 < target) {
               left++;
            } else {
               right--;
            }
        } 
    }
}

class Solution {
    public int[] twoSum(int[] numbers, int target) {
       int left = 0;
       int right = numbers.length - 1;
        
        while (left < right) {
        //code

            if (param1 == param2) {
            // code 
        
                left++;
                right--;
            } else if (param1 < param2) {
               left++;
            } else {
               right--;
            }
        } 
    }
}

Step 2 : – I/O parameters.

Input parameters :- To calculate the value of param1, we add the values of the elements at the left and right indices. This sum becomes our currentSum and replaced param2 with the target value.
Output Parameter :- We should return the result immediately once currentSum matches the target value, so there’s no need to increment left or decrement right inside the equality block.
If none of the three conditions in the code are met, we should return [-1, -1].

Java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
       int left = 0;
       int right = numbers.length - 1;
        
        while (left < right) {
            int currentSum = numbers[left] + numbers[right];
            if (currentSum == target) {
                return new int[] {left + 1, right + 1};
                //left++;
                //right--;
            } else if (currentSum < target) {
               left++;
            } else {
               right--;
            }
            // This should not be reached based on the problem statement
            return new int[] {-1, -1};
        } 
    }
}

class Solution {
    public int[] twoSum(int[] numbers, int target) {
       int left = 0;
       int right = numbers.length - 1;
        
        while (left < right) {
            int currentSum = numbers[left] + numbers[right];
            if (currentSum == target) {
                return new int[] {left + 1, right + 1};
                //left++;
                //right--;
            } else if (currentSum < target) {
               left++;
            } else {
               right--;
            }
            // This should not be reached based on the problem statement
            return new int[] {-1, -1};
        } 
    }
}

Final Code : –

Java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
      int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int currentSum = numbers[left] + numbers[right];

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

        // This should not be reached based on the problem statement
        return new int[] {-1, -1};
    }
}

class Solution {
    public int[] twoSum(int[] numbers, int target) {
      int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int currentSum = numbers[left] + numbers[right];

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

        // This should not be reached based on the problem statement
        return new int[] {-1, -1};
    }
}