Last Updated: 8 Sep, 2020
Pair Sum
Easy
Asked in companies
You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to return the list of all pairs of elements such that each sum of elements of each pair equals 'S'.
Note:
Each pair should be sorted i.e the first value should be less than or equals to the second value.
Return the list of pairs sorted in non-decreasing order of their first value. In case if two pairs have the same first value, the pair with a smaller second value should come first.
Input Format:
The first line of input contains two space-separated integers 'N' and 'S', denoting the size of the input array and the value of 'S'.
The second and last line of input contains 'N' space-separated integers, denoting the elements of the input array: ARR[i] where 0 <= i < 'N'.
Output Format:
Print 'C' lines, each line contains one pair i.e two space-separated integers, where 'C' denotes the count of pairs having sum equals to given value 'S'.
Note:
You are not required to print the output, it has already been taken care of. Just implement the function.
Constraints:
1 <= N <= 10^3
-10^5 <= ARR[i] <= 10^5
-2 * 10^5 <= S <= 2 * 10^5
Time Limit: 1 sec
Approaches
- Initialize a list to store our results.
- For each element in the array 'ARR[i]', check if ('ARR[i]' + ‘ARR[j]’), equals to given sum or not, where ‘i’ < ‘j’ < ‘N’.
- If the condition matches, add the pair('ARR[i]', ‘ARR[j]’) to the list. Sort the list of pairs as per the given output format and return this list.
- Initialize a list to store our results.
- For each element in the array ‘ARR[i]’, we will check whether there exists an element equals to ('S' - ‘ARR[i]’) already in the map.
- If it exists we will add the pair('ARR[i]', ‘S’ - ‘ARR[i]’ ) ‘COUNT’ number of times to the list, where ‘COUNT’ represents the frequency of ('S' - ‘ARR[i]’) in the map.
- Also, we will increment the frequency of the current element ('ARR[i]') in the map. Sort the list of pairs as per the given output format and return this list.
We will create a map where the key is the unique element in the ‘ARR’ and value is the number of times that key appeared in the ‘ARR’. We will create a ‘KEYARRAY’ to store all the unique elements in the ‘ARR’.
We will first sort the ‘KEYARRAY’ and for every ‘KEY’ in ‘KEYARRAY’ we will check if ‘KEY’ + ‘KEY’ is equal to the target sum. If yes we will add all the occurrences of the ‘PAIR’ = {‘KEY’, ‘KEY’) in the answer list. Total such possible pairs are given by the formula N*(N-1)/2.
For example, if ‘ARR’ = {2, 2, 2}, ‘S’ = 4. Then ‘MAP’ = {[2, 4]}, ‘KEYARRAY’ = {2} and ‘ANS’ = {[2, 2], [2, 2], [2, 2]}.
Then we will maintain two pointers ‘LOW’ and ‘HIGH’ pointing to the start and end of the ‘KEYARR’. We will find the current sum, which will be ‘KEYARR[LOW]’ + ‘KEYARR[HIGH]’ and if the current sum is equal to the target sum then we will add all the occurrences of the current pair to our answer list. Otherwise, if the current sum is less than the target sum we will increment ‘LOW’ by 1 so that we can get a greater current sum in the next iteration. Otherwise, if the current sum is greater than the target sum we will decrement ‘HIGH’ by 1 so that we can get a lesser current sum in the next iteration.
Algorithm:
- Initialize a list ‘ANS’ to store the result.
- Initialize a map ‘MAP’.
- Iterate ‘NUM’ in ‘ARR’:
- Add ‘NUM’ to the ‘MAP’ and increment its value by 1.
- Initialize a list ‘KEYARRAY’ to store the unique elements in ‘ARR’.
- Iterate ‘KEY’ in ‘KEYARRAY’
- If ‘KEY’ + ‘KEY’ is equal to ‘S’, add all such pairs([‘KEY’, ‘KEY’]) to the ‘ANS’.
- Initialize two pointers ‘LOW’ and ‘HIGH’ pointing to the left and right end of ‘KEYARRAY’ respectively.
- Iterate while ‘LOW’ is less than ‘HIGH’:
- Set ‘CURRSUM’ as ‘KEYARRAY’[‘LOW’] + ‘KEYARRAY’[‘HIGH’].
- If ‘CURRSUM’ is equal to ‘S’, add all such pairs([‘KEYARRAY’[‘LOW’], ‘KEYARRAY’[‘HIGH’]]) to ‘ANS’.
- Increment ‘LOW’ by 1.
- Decrement ‘HIGH’ by 1.
- Otherwise, if ‘CURRSUM’ is less than ‘S’:
- Increment ‘LOW’ by 1.
- Otherwise,
- Decrement ‘HIGH’ by 1.
- Sort the list of pairs as per the given output format and return this list.