About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

2 Sum In A Sorted Array Problem

Problem Statement:

Given a non decreasing order sorted array, return two indices whose value from array adds up to the given target value. The same element can not be used twice.

Note:

1. If problem has multiple answers you can return any one of them.

2. Order of indices in returned answer doesn’t matter,

Input Format:

There are two arguments in input. The first argument will be an integer array arr and the second argument will be an integer target.

Output Format:

Return an integer array of size representing array indices which sums to the given target value. In case of no answer return arr of size two with elements -1 and -1.

Constraints:

● 1

● 0

● 1

● Array can contain duplicate elements.

Solution

We have provided solutions which contain necessary comments to understand the approaches used:

1) hashing_solution.java

Description:

As we need to find two indices whose value from array adds up to the given target value. And we can not use the same element twice.

As we know given array is sorted, If the question was only two check if solution exists or not we could have done it using binary search but as we are concerned about indices as well we will use hashing based solution.

We will maintain a hashmap where key will be number and value will be index of that value in given array.

Now, we will iterate over the array and check for current value num whether target-num exist in the array or not.

If exist then index of current num and index of target-num value in the array will be our answer.

If doesn’t exist then we will add current num, current index in the hashmap and continue the iteration.

In case if we didn’t find any answer we will return [-1, -1] as the answer.

Time Complexity:

O(n) where n is the size of given unsorted array.

As we are iterating over array of size n and using the operation of get/put/containsKey n times in the worst case which will take O(1) per operation hence total complexity will be O(n) + O(n) → O(n).

Auxiliary Space Used:

O(n) where n is the size of given unsorted array.

We are storing num mapped to their index in hashmap and in the worst case when no solution found and array contained all distinct elements, it will require O(n) space. Hence auxiliary space used will be O(n).

Space Complexity:

O(n) where n is the size of given unsorted array.

To read input it will take O(n) as we are reading an array of size n, auxiliary space used is O(n) and to store output it will take O(1) hence total space complexity will be O(n) + O(n) + O(1) → O(n).


// -------- START --------
class Result {

    public static List sum_in_a_sorted_array(List arr, int target) {
        List ans = new ArrayList();

        // To store number with it's index in the array
        HashMap map = new HashMap(); 
        for (int i=0; i

2) sliding_window_solution.java

Description:

As we need to find two indices whose value from array adds up to the given target value. And we can not use the same element twice.

In this solution we will leverage the fact that array is already sorted in non decreasing order. We will use sliding window algorithm.

We will maintain two pointers left and right, initially initialised to start and end of the array respectively.

We will iterate till left pointer < right pointer.

1. If we found arr[l] + arr[r] = target, then [l, r] will be our answer.

2. If we found arr[l] + arr[r] < target then we will increment l as we want to reach target value and for that we need a bigger value then what we currently have.

3. If we found arr[l] + arr[r] >= target then we will decrement r as we want to reach target value and for that we need a smaller value then what we currently have.

If after complete iteration if we didn’t find any solution then we will return [-1, -1].

Time Complexity:

O(n) where n is the size of given non decreasing sorted array.

As we are iterating over array of size n and using just doing comparison operation n times which will take O(1) per operation hence total complexity will be O(n) + O(n) → O(n).

Auxiliary Space Used:

O(1).

We are just iterating over given array and not storing anything extra.

Space Complexity:

O(n) where n is the size of given unsorted array.

To read input it will take O(n) as we are reading an array of size n, auxiliary space used is O(1) and to store output it will take O(1) hence total space complexity will be O(n) + O(1) + O(1) → O(n).


// -------- START --------
class Result {

    public static List sum_in_a_sorted_array(List arr, int target) {
        /* Sort the elements */
        List ans = new ArrayList();

        /* Now look for the two candidates
        in the sorted array*/
        int l = 0, r = arr.size() - 1;
        while (l < r) {
            if (arr.get(l) + arr.get(r) == target) {
                ans.add(l);
                ans.add(r);
                return ans;
            }
            else if (arr.get(l) + arr.get(r) < target) {
                l++;
            }
            else {// A[i] + A[j] > target 
                r--;
            }
        }
        ans.add(-1);
        ans.add(-1);
        return ans;
    }
}
// -------- END --------