2 Sum In A Sorted Array Problem

Two sum is a super popular interview problem asked at FAANG companies like Amazon, Facebook, and Google. The goal of the two sum problem is simple — find two indices from a given array that add up to a given target value.
We’ll look at three ways of solving this problem — brute force, hashing, and two pointers.
Let’s get started!

2 Sum In A Sorted Array Problem Statement

Given an array sorted in non-decreasing order and a target number, find the indices of the two values from the array that sum up to the given target number.

Example

{
"numbers": [1, 2, 3, 5, 10],
"target": 7
}

Output:

[1, 3]

Sum of the elements at index 1 and 3 is 7.

Notes

• In case when no answer exists, return an array of size two with both values equal to -1, i.e., [-1, -1].
• In case when multiple answers exist, you may return any of them.
• The order of the indices returned does not matter.
• A single index cannot be used twice.

Constraints:

• 2 <= array size <= 10⁵
• -10⁵ <= array elements <= 10⁵
• -10⁵ <= target number <= 10⁵
• Array can contain duplicate elements.

We have provided three solutions.

Throughout this editorial, we will refer to the input array as numbers, its size as numbers_size and the target integer as target.

2 Sum In A Sorted Array Solution 1: Brute Force

In the brute force solution, we will run two nested loops and check the sum of every pair of elements present in the array. If any pair sums up to the target, we will return the indices of that pair of elements.

Otherwise, we will return [-1, -1].

Time Complexity

O((numbers_size)²).

Total number of possible pairs: (numbers_size * (numbers_size - 1)) / 2.

Auxiliary Space Used

O(1).

Space Complexity

O(numbers_size).

Space used for input: O(numbers_size).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(numbers_size).

Code For 2 Sum In A Sorted Array Solution 1: Brute Force

    /*
    * Asymptotic complexity in terms of the size of `numbers` ( = `n`):
    * Time: O(n^2).
    * Auxiliary space: O(1).
    * Total space: O(n).
    */

    static ArrayList<Integer> pair_sum_sorted_array(ArrayList<Integer> numbers, Integer target) {

        // A list to store the pair of indices that adds to target.
        ArrayList<Integer> result = new ArrayList<Integer>();

        for (int i = 0; i < numbers.size(); i++) {
            // For every element in numbers we find its complementary pair that sum to
            // target.

            for (int j = i + 1; j < numbers.size(); j++) {

                // If target pair indices found.
                if (numbers.get(i) + numbers.get(j) == target) {

                    // Add them to result list and return.
                    result.add(i);
                    result.add(j);
                    return result;
                }
            }
        }

        // If no such pair of indices exist, add -1, -1 to list.
        result.add(-1);
        result.add(-1);
        return result;
    }

2 Sum In A Sorted Array Solution 2: Hashing

While iterating through the array, let’s say we are at a number current. Being at this number, we need to check whether target - current has occurred at a smaller index in the array or not.

To check the occurrence of target - current, one way is to run another loop on the array to linearly search for that element. But as discussed above, this won’t be efficient.

Note that the array is sorted. So, another approach is to perform a binary search on the array from index 0 to the current index – 1 to check whether target - current has occurred in the array or not. This binary search will be O(log(numberssize)) in the worst case. Hence, the overall runtime of this approach would be O(numberssize * log(numbers_size)). We can do even better than this. We can check whether target - current has previously occurred in the array or not in O(1) time using hashing.

We will maintain a hashmap which stores the index of an element present in the array and will keep building this hashmap as we iterate through the array. Now, being at any number current, we will use this hashmap to check whether target - current has previously occurred in the array or not.

Time Complexity

O(numbers_size).

We iterate through each element in the numbers array exactly once and are doing a constant amount of work in each iteration.

Auxiliary Space Used

O(numbers_size).

At most, we will be storing all the elements in the hashmap.

Space Complexity

O(numbers_size).

Space used for input: O(numbers_size).

Auxiliary space used: O(numbers_size).

Space used for output: O(1).

So, total space complexity: O(numbers_size).

Code For 2 Sum In A Sorted Array Solution 2: Hashing

    /*
    * Asymptotic complexity in terms of the size of `numbers` = `n`:
    * Time: O(n).
    * Auxiliary space: O(n).
    * Total space: O(n).
    */

    static ArrayList<Integer> pair_sum_sorted_array(ArrayList<Integer> numbers, Integer target) {
        // A list to store the pair of indices that adds to target.
        ArrayList<Integer> result = new ArrayList<Integer>();

        // This Map stores the array element as Key and its index as Value.
        HashMap<Integer, Integer> array_index = new HashMap<Integer, Integer>();

        for (int i = 0; i < numbers.size(); i++) {
            int current = numbers.get(i);
            int required = target - current; // complementary target pair

            if (array_index.containsKey(required)) {
                result.add(array_index.get(required)); // store index of required in result
                result.add(i);
                return result;
            }

            // Add every element to map after checking for required.
            // This ensures element does not math itself (indices to be unique).
            array_index.put(current, i);
        }

        // If no such pair of indices exist, add -1, -1 to list.
        result.add(-1);
        result.add(-1);
        return result;
    }

2 Sum In A Sorted Array Solution 3: Two Pointers

The above solution does not make use of the fact that the input array is sorted and works well even in the case of an unsorted array. We can make use of this fact to reduce the auxiliary space usage of our solution.

Say, we pick any two indices in the array and check the sum of their values. There may arise three possibilities regarding the sum of those two values:

• The sum is equal to target: In this case, we are lucky enough and will return the two selected indices.
• The sum is less than target: In this case, we would want to increase the sum. Since the array is sorted, we can increase the sum by moving one of the indices towards right.
• The sum is greater than target: In this case, we would want to decrease the sum. This can be done by moving one of the indices towards the left.

So, the idea is to initially have pointers on the leftmost and the rightmost indices of the array. We will be using the left pointer to increase the sum and the right pointer to decrease the sum whenever needed. Therefore, the left pointer will move towards the right and the right pointer will move towards the left till one of the following conditions get satisfied:

1. The sum of the values pointed by the left and the right pointers is equal to target.
2. The two pointers cross each other. In this case, no valid pair exists in the array.

Time Complexity

O(numbers_size).

We will be traversing through each index at most once.

Auxiliary Space Used

O(1).

We have only used some constant amount of extra space.

Space Complexity

O(numbers_size).

Space used for input: O(numbers_size).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(numbers_size).

Code For 2 Sum In A Sorted Array Solution 3: Two Pointers

    /*
    * Asymptotic complexity in terms of the size of `numbers` = `n`:
    * Time: O(n).
    * Auxiliary space: O(1).
    * Total space: O(n).
    */

    static ArrayList<Integer> pair_sum_sorted_array(ArrayList<Integer> numbers, Integer target) {
        // A list to store the pair of indices that adds to target.
        ArrayList<Integer> result = new ArrayList<Integer>();

        int left = 0, right = numbers.size() - 1;

        while (left < right) {
            // Current sum is the sum of numbers at left and right indices.

            if (numbers.get(left) + numbers.get(right) == target) {
                result.add(left);
                result.add(right);
                return result;
            }
            // If the current sum is less than target, move left to (left + 1).
            // Element at (left + 1) is greater than the element at left, as the given array is sorted.
            else if (numbers.get(left) + numbers.get(right) < target) {
                left++;
            }
            // If the current sum is more than target, move right to (right - 1).
            // Element at (right - 1) is less than the element at right.
            else {
                right--;
            }
        }

        // If no such pair of indices exist, add -1, -1 to list.
        result.add(-1);
        result.add(-1);
        return result;
    }

We hope that these solutions to two sum in a sorted array problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.