Two Sum II - Input Array Is Sorted

Leetcode Problem: Two Sum II - Input Array Is Sorted

Objective:

Given a sorted array and target sum, find the two indexes that add up to the target sum.

Pattern: Two Pointer Technique

Approach:

1. Have one pointer at the start and one pointer at the end of the array.
2. Initialize the output int [] array with a size of 2, for the two indexes.
3. Use a while loop with the condition where start < end, since the start index should never be greater than the end index. This means we have already checked all elements from left and right side.
4. Inside while loop, check if the current sum is equal to the target. If it is, return the indexes.
5. If the current sum is less than target, increment the start index.
6. If the current sum is greater than target, decrement the end index.

Big-O Notation:

Time Complexity: O(n)
We have iterate through the while loop n times, for each element.

Space Complexity: O(1)
We do not use any additional data structures for storage.

Code:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // use two pointer techique because the input is sorted.
        int start = 0; 
        int end = numbers.length - 1;
        int [] result = new int [2];

        while (start < end){
            int sum = numbers[start] + numbers[end];

            if (sum == target){
                result[0] = start + 1;
                result[1] = end + 1;
                break;
            }

            if (sum < target){
                start++;
            } else {
                end--;
            }
        }
        return result;
    }
}