Pair Sum
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

Question

Pair Sum

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

Accepted Answer

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).

Accepted Answer

The problem can be solved in O(n) time using hashing.
Use a hashset to check for the current array value. Check if targetsum – current value exists in the map or not. If it exists, that means a pair with sum equal to target sum exists in the array.

Accepted Answer

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).

Accepted Answer

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).

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:

Input Format:

Output Format:

Note:

Constraints:

Top Morgan Stanley Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Morgan Stanley Software Developer