Pair Sum

#### 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
``````
#TataConsultancyServices(Tcs)#AssociateSoftwareEngineer CodingNinjas
Answered Mar 09, 2022
Brute Force
• 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.
Space Complexity: O(1)Explanation:

O(1).

Constant extra space is required.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the number of elements in the array.

In the worst case, for each element, we will be checking all other elements in the array. Hence the overall time complexity will be O(N ^ 2).

Report CodingNinjas
Answered Mar 09, 2022
Using HashMap
• 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.
Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of elements in the array.

In the worst case, O(N) extra space is required for the hashmap to store the frequency of each element. Hence the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N^2), where ‘N’ is the number of elements in the array.

For the worst case, when all elements are the same we must have to add ‘N’^2 pairs to the answer vector and so, the overall time complexity will be O(N^2).

Report CodingNinjas
Answered Mar 09, 2022
Two Pointers

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.
Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of elements in the array.

In the worst case, O(N) extra space is required for the hashmap to store the unique elements and frequency of each element. Hence the overall space complexity will be O(N).

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of elements in the given array.

For the worst case, when all elements are the same we must have to add ‘N’^2 pairs to the answer vector and so, the overall time complexity will be O(N^2).

Report