Two Sum II - Input Array Is Sorted

Moderate
0/80
profile
Contributed by
9 upvotes
Asked in companies
Robert Bosch Engineering and Business Solutions VietnamCredit SuisseQuest Global Pvt. Services Ltd

Problem statement

Given an array ‘A’ of size ‘N’, sorted in non-decreasing order. Return the pair of two distinct indices whose value adds up to the given ‘target’. The given array is 0 indexed. So returned indices are in the range [0, N-1], both inclusive. If there are multiple answers, you can return any.

For example: 
Suppose ‘N’ = 5, ‘A’ = [1,2,3,4,5], and target = 8
As target == A[2] + A[4] = 3 + 5 = 8.
Hence output will be 2 4.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘Target’, denoting the size of ‘A’ and the target sum value.

The second line of each test case contains ‘N’ space-separated integers representing the elements of ‘A’.

Output Format:

For each test case, print two space-separated integers denoting the indices of elements of ‘A’, which add up to ‘target’.

Print a separate line for each test case.
Note 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints -

1 ≤ T ≤ 1000
1 ≤ N ≤ 100000
-1000 ≤ A[i] ≤ 1000
ΣN ≤ 300000

Time limit: 1 Sec
Sample Input 1 :
2
5 8
1 2 3 4 5
4 4
2 2 4 5
Sample Output 1 :
2 4
0 1
Explanation For Sample Input 1 :
For First Case - Same as explained in above example.

For the second case - 

‘N’ = 4, ‘A’ = [2,2,4,5], and target = 4
As target == A[0] + A[1] = 2 + 2 = 4.
Hence output will be 0 1.
Sample Input 2 :
3 8
1 7 8
2 10
1 9
Sample Output 2 :
1 0
0 1
Hint

We can search for its complement with the target sum for each element. (Complement of i = target - A[i])

Approaches (1)
Two Pointers

We are using a classical approach of two pointers. The inspiration for this kind of approach simply comes from the fact that A[i] + A[j] == target, then for any index k > i. Its complement can only be in the range <= j, which further translates to the following lemma- “for the increasing value of i the index of its complement can only decrease”. Thus we can keep two pointers at the start for i and the other j at the end for the complement. As we can only decrease j at most O(N) times and increase i O(N) times, the time should also be linear. Implementation details will be as per the following algorithm.

 

Algorithm: 

The steps are as follows:

  • Declare and initialize integer n = size of ‘A’
  • Declare and initialize integers i = 0 and j = n-1
  • Declare integer array ans of size 2
  • Iterate over i from 0 to n-1 while j > i
    • While j > i AND A[i]+A[j] > target
      • Decrement j by one
    • If A[i] + A[j] == target
      • ans = [i, j]
      • Break
  • Return ans
Time Complexity

O(N) where N is the size of given array ‘A’.

 

As explained in the algorithm part, we will be increasing i at most O(N) times and decreasing j O(N) times which makes the total complexity to be O(N) + O(N) = O(N).

Space Complexity

O(1)

 

We don’t need extra space other than a few constant space variables like ans, i, j, and n.

Code Solution
(100% EXP penalty)
Two Sum II - Input Array Is Sorted
Full screen
Console