Last Updated: 20 Nov, 2020
3Sum
Moderate
Asked in companies
You are given an array/list ARR consisting of N integers. Your task is to find all the distinct triplets present in the array which adds up to a given number K.
An array is said to have a triplet {ARR[i], ARR[j], ARR[k]} with sum = 'K' if there exists three indices i, j and k such that i!=j, j!=k and i!=j and ARR[i] + ARR[j] + ARR[k] = 'K'.
Note:
1. You can return the list of values in any order. For example, if a valid triplet is {1, 2, -3}, then {2, -3, 1}, {-3, 2, 1} etc is also valid triplet. Also, the ordering of different triplets can be random i.e if there are more than one valid triplets, you can return them in any order.
2. The elements in the array need not be distinct.
3. If no such triplet is present in the array, then return an empty list, and the output printed for such a test case will be "-1".
Input Format:
The first line of the input contains an integer T, denoting the number of test cases.
The first line of each test case contains the integer N, denoting the size of the array.
The second line of each test case contains N space-separated integers denoting the array elements.
The third line of each test case contains the integer K, denoting the required sum for each triplet.
Output Format:
For each test case, every line of output contains three spaced integers denoting a valid triplet as described in the statement. Refer to sample input 2 for more clarification.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10^3
-10^6 <= ARR[i] <= 10^6
-10^9 <= K <= 10^9
Time Limit: 1 sec
Approaches
- The most trivial approach would be to find all triplets of the array and count all such triplets whose ‘SUM’ = 'K'.
- We can find the answer using three nested loops for three different indexes and check if the values at those indexes sum up to 'K'.
- Create a set to keep the track of triplets we have visited. Run first loop from i = 0 to i = ‘N’ - 3, second loop from j = i + 1 to j = ‘N’ - 2 and third loop from ‘K’ = j + 1 to ‘K’ = ‘N’ - 1.
- Check if ‘ARR[i]’ + ‘ARR[j]’ + ‘ARR[K]’ = ‘K’
- If the triplet is not present in the set, then print the triplet and insert the triplet into the set since we need distinct triplets only.
- Else continue.
- Sort the array in non-decreasing order because after the array is sorted, we don’t have to process the same elements multiple times and hence we don’t have to explicitly keep track for distinct triplets. The other advantage of sorting the array is that if we have some value and we require a greater value, we know we have to look in only a single direction.
- Now since we want triplets such that x + y + z = ‘K’, we have x+ y = ‘K’ - z and now we can fix z as arr[i]. So we want to find the sum of two numbers x and y as ‘K’ - arr[i] in the array.
- Let us assume that we are the ith index of the array and initialise variable target to ‘K’ - ‘ARR[i]’.
- So now we just need to find two elements x, y such that target = x + y.
- We will use two pointers, one will start from i+1, and the other will start from the end of the array.
- Let the two pointers be ‘FRONT’ and ‘BACK’, where ‘FRONT’ = i + 1 and ‘BACK’ = n - 1. Let ‘SUM’ = x + y, where x = ‘ARR[FRONT]’ and y = ‘ARR[BACK]’. We have to find the triplets such that ‘TARGET’ = ‘SUM’.
- While ‘FRONT’ < ‘BACK’, there will be 3 cases:
- if ('SUM' < ‘TARGET’), we will have to increase the sum and hence increment front pointer as we have sorted the array and to increase the sum, the greater element will always be present after the front index.
- Else if ('SUM' > ‘TARGET’), we will have to decrease the sum and hence decrease the ‘BACK’ pointer. The reason for this is exactly similar to the above point
- Else print the triplet and since we want distinct triplets, do the following.
- Increment the front pointer until ‘ARR[FRONT]’ = x and ‘FRONT’ < ‘BACK’.
- Decrement the back pointer until ‘ARR[BACK]’ = y and ‘FRONT’ < ‘BACK’.
- While ‘ARR[i]’ = ‘ARR[i+1]’, keep on incrementing i, this will automatically ensure that we are only finding distinct triplets.
Similar problems
Longest Subarray With Zero Sum
Moderate
Posted: 3 Nov, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Ninja And The Strictly Increasing Array
Moderate
Posted: 27 Nov, 2022
Negative To The End
Easy
Posted: 16 Dec, 2022
Find Duplicate in Array
Easy
Posted: 5 Jun, 2023