Two Sum II - Input Array Is Sorted

NeetCode: Two Sum II - Input Array Is Sorted · LeetCode: 167. Two Sum II - Input Array Is Sorted · Difficulty: Medium

Given a sorted array numbers (1-indexed in the problem statement), find two numbers that add up to target and return their 1-based indices [i, j] with i < j. Exactly one solution exists. Use only constant extra space.

Example

Text

Input:  numbers = [1, 2, 3, 4], target = 3    Output: [1, 2]

Brute force: binary search for each partner

For each numbers[i], binary search the rest of the array for target - numbers[i]. Arrays.binarySearch(array, from, to, key) searches the range [from, to) and returns the index of a match, or a negative number when the key is absent. The subtraction is an int operation that wraps on overflow, so inputs near the int limits need long; the examples are small.

Java

import java.util.Arrays;

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int need = target - numbers[i];
            // Searches numbers[i + 1 .. n - 1]; returns a negative number when absent.
            int j = Arrays.binarySearch(numbers, i + 1, numbers.length, need);
            if (j >= 0) {
                return new int[]{i + 1, j + 1};
            }
        }
        return new int[0];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.twoSum(new int[]{1, 2, 3, 4}, 3)));
        System.out.println(Arrays.toString(s.twoSum(new int[]{2, 7, 11, 15}, 9)));
    }
}

Output

[1, 2]
[1, 2]

Time: O(n log n). Space: O(1).

Optimal: two pointers

Start with left at the smallest value and right at the largest. If the sum is too small, only moving left right can raise it. If it is too big, only moving right left can lower it. Every step rules out one element for good.

Java

import java.util.Arrays;

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.twoSum(new int[]{1, 2, 3, 4}, 3)));
        System.out.println(Arrays.toString(s.twoSum(new int[]{2, 7, 11, 15}, 9)));
    }
}

Output

[1, 2]
[1, 2]

Time: O(n). Space: O(1). The sum is computed in long, so two large values cannot wrap around. The method returns an empty array if no pair exists, although the problem guarantees one.