Solving Two Sum II - Input Array Is Sorted

To see the question, click here.

Naive Approach

The idea is to check all possible pairs to ensure that the sum of the numbers at those pointers equals the target. So, maintain two pointers i and j at the first two positions of the array and return the indices once the sum is equal to the target.

// TC: O(n^2)
// SC: O(1)

public class TwoSumII {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    result[0] = i + 1;
                    result[1] = j + 1;
                    break;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        TwoSumII ts = new TwoSumII();
        int[] numbers = { 2, 7, 11, 15 };
        int target = 9;
        int[] result = ts.twoSum(numbers, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

Performance

The time complexity of the twoSum method is O(n^2) because there are two nested loops iterating over the input array numbers. The space complexity is O(1) because the method only uses constant extra space to store the result array.

Refined Approach

numbers[i] + numbers[j] = target

numbers[j] = target - numbers[i]

The idea is to remember the values of numbers[j]. So, maintain a pointer i at the first position of the array. Create a HashMap where the keys represent the numbers at the ith position and values represent the indices i. Start iterating and check if numbers[j] exists in the HashMap. If it doesn't, then add the element to the HashMap . If exists, then it means that numbers[j] has already been visited, so return the indices. For the sake of convenience, consider numbers[j] as diff.

// TC: O(n)
// SC: O(n)

import java.util.Map;
import java.util.HashMap;

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

    public static void main(String[] args) {
        TwoSumII ts = new TwoSumII();
        int[] numbers = { 2, 7, 11, 15 };
        int target = 9;
        int[] result = ts.twoSum(numbers, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

Performance

The time complexity of the twoSum method is O(n) because we iterate through the array of numbers once to find the two numbers that add up to the target. The space complexity is also O(n) because we use a HashMap to store the numbers and their indices, potentially storing all the numbers in the array.

Efficient Approach

Since the array is sorted, let us try out the two-pointer technique. Assume that the sum of the numbers at those two pointers is less than the target. It means that to reach the target, we have to look for the number which is greater than the number at ith position. So increment i to the next position. This is the key step because moving i will increase the chances of reaching the target as the array is sorted. In a similar way, if the sum of the numbers at those two pointers is greater than the target, decrement j to the next position. Once the target is reached, return the indices.

// TC: O(n)
// SC: O(1)

public class TwoSumII {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        int[] result = new int[2];

        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) {
                result[0] = i + 1;
                result[1] = j + 1;
                break;
            } else if (sum < target) {
                i++;
            } else {
                j--;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        TwoSumII ts = new TwoSumII();
        int[] numbers = { 2, 7, 11, 15 };
        int target = 9;
        int[] result = ts.twoSum(numbers, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

Performance

The time complexity of the twoSum method is O(n) because we are iterating through the array of numbers only once using two pointers i and j which move towards each other until they meet. The space complexity is O(1) because we use constant extra space to store the result array.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.