Given an array of integers A[], find two numbers such that they add up to a specific target number B.

The program should return indices of the two numbers such that they add up to the target, where index1 < index2. Please note that your returned answers (both index1 and index2 ) are not zero-based.

Put both these numbers in order in an array and return the array from your function. Note that, if no pair exists, return an empty list.

If multiple solutions exist, output the one where index2 is minimum. If there are multiple solutions with the minimum index2, choose the one with minimum index1 out of them.

Solution

There are many solutions to the problem.

Solution 1: Sorting Based
1. Sort the array in non-decreasing order. 2. Initialize two index variables to find the candidate elements in the sorted array. (a) Initialize first to the leftmost index: l = 0 (b) Initialize second the rightmost index: r = ar_size-1 3. Loop while l < r. (a) If (A[l] + A[r] == sum) then return 1 (b) Else if( A[l] + A[r] < sum ) then l++ (c) Else r-- 4. No candidates in whole array - return 0

Time Complexity : O(nlogn)

Space Complexity : O(1)

Solution 2: Hashing Based
With hashing, we can get a linear time complexity solution. 1. Maintain HashMap for all Integer with Key as B-A[i] and Value as Index i. 2. Before insert, check that number is already present in Map. If YES, Return current index as index2 and index1 from Map entry. If NO, Insert new entry to the map.

Time Complexity : O(n)

Space Complexity : O(n)

Output

[1, 2]

We acknowledge you to write a comment if you have a better solution or having any doubt on the above topic.