Two Sum II - Input Array Is Sorted

Moderate
0/80
profile
Contributed by
10 upvotes
Asked in companies
Quest Global Pvt. Services LtdRobert Bosch Engineering and Business Solutions VietnamCredit Suisse

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