Last Updated: 20 Nov, 2020
2 Sum
Moderate
Asked in companies
Given an integer array Arr of size N and an integer target, your task is to find the indices of two elements of the array such that their sum is equal to target. Return <-1,-1> if no such pair exists.
Note:
If more than one such pair of indices exist, return the lexicographically smallest pair
You may not use the same element twice.
Input format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first line of each test case or query contains an integer 'N' representing the size of the array (Arr).
The second line contains 'N' single space-separated integers, representing the elements in the array.
The third line contains the value of the target.
Output format:
For each test case, print the indices of the elements from the array whose sum is equal to the target.
The output for each test case is printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
2 <= N <= 5 * 10^4
-10^5 <= Arr[i] <= 10^5
2 * (-10^5) <= target <= 2 * 10^5
Where T is the number of test cases, N is the size of the input array, Arr[i] refers to the elements of the array and target is the given value of the sum.
Approaches
The idea is to explore all the possible pairs of indices of the array and check whether the sum of any of the pair elements sums up to the target value.
Algorithm :
- Create two nested loops with counter i and j respectively.
- First loop will run from 0 to N-1 and second loop will run from i+1 to N-1
- Check if the sum of the elements present at the ith index and the jth index is equal to the target value or not.
- Print the indices of the pair, if found, else return {-1,-1}.
The idea is to check if target - Arr[i] exists for any element x in the array. This lookup of target - Arr[i] can be accomplished by creating a hash table, such that the key is the element of the array and the corresponding value is the list of indices at which the element is present.
A simple implementation uses two iterations. In the first iteration, we add each element’s value and its index to the hash table. Then, in the second iteration we check if each element’s complement (target - Arr[i]) exists in the table. Beware that the complement of an element Arr[i] is not the same element itself i.e. the complement should be present at any index other than ‘i’.
Algorithm :
- Create a hash table and for every element in the array:
- If the element does not exist in the hash map, add the element and its corresponding index in the map.
- If it is already present, add the current index to the list of indices mapped by the current element.
- Take a variable of type pair to store the values of indices of the required pair.
- Iterate over the whole array again and using the hash table created in step 1 check whether target - Arr[i] is present in the hash table or not.
a. If the value is present in the hash table, iterate over the list of indices mapped by the value till you find an index that is not equal to ‘i’. If you find such a value, we have found a pair that sums to target. Update the value of the pair. - Return the pair.
Note: We are traversing the array and adding the indices in the hash map. Thus, the list of indices mapped by an element in the map will always be sorted. Thus, the first pair that we find in step 3 will be the lexicographically smallest.
We can use hashing to find the required pair of indices in one-pass. The hash map will have the value of the elements of the array as key and the first occurring index of the element as the value corresponding to the key.
While we are iterating and inserting elements into the table, we also look back to check if (target - current element) already exists in the table. If it exists, we have found a solution and return immediately, else we keep on iterating and filling our hash table.
Algorithm :
- Create a hash table and take a variable of type pair to store the indices of the required pair.
- Iterate the array and check if target - Arr[i] exits in the hash table.
a. If it exists, update the value of the pair if this is the first pair that we have found or this is the lexicographically smallest pair until now.
b. Else insert the current index value in the hash map only if no such key already exists in the hash map and continue the iteration. - Return the pair.