167. Two Sum II - Input array is sorted

Description

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• Your returned answers (both index1 and index2) are not zero-based.

• You may assume that each input would have exactly one solution and you may not use the same element twice.

Constraints

• 2 <= nums.length <= 3 * 104

• -1000 <= nums[i] <= 1000

• nums is sorted in increasing order.

• -1000 <= target <= 1000

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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.

Example 2

Input: numbers = [2, 3, 4], target = 6

Output: [1, 3]

Example 3

Input: numbers = [-1, 0], target = -1

Output: [1, 2]

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> indexMap = new HashMap();
        int[] result = new int[2];
        for(int i = 0; i < numbers.length; i++) {
            int diff = target - numbers[i];
            if(indexMap.containsKey(diff)) {
                result[0] = indexMap.get(diff);
                result[1] = i+1;
                break;
            } else {
                indexMap.put(numbers[i], i+1);
            }
        }
        return result;
    }
}

Solution 2

/**
 * Time complexity : O(n). Each of the n elements is visited at most once, 
 *    thus the time complexity is O(n).
 * Space complexity : O(1). We only use two indexes.
 */
 
 class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        int leftPtr = 0, rightPtr = numbers.length-1;
        
        while(leftPtr < rightPtr) {
            int sum = numbers[leftPtr]+numbers[rightPtr];
            if(sum == target) {
                result[0] = leftPtr+1;
                result[1] = rightPtr+1;
                break;
            } else if(sum > target) {
                rightPtr--;
            } else {
                leftPtr++;
            }
        }
        
        return result;
    }
}

Follow up