Last Updated: 24 Nov, 2022
Three Sum
Moderate
Asked in company
You are given an array ‘ARR’ containing ‘N’ integers.
Return all the unique triplets [ARR[i], ARR[j], ARR[k]] such that i != j, j != k and k != i and their sum is equal to zero.
Example:
Input: ‘N’ = 5
'ARR' = [-1, -1, 2, 0, 1]
Output:
-1 -1 2
-1 0 1
Explanation:
(-1 -1 +2) = (-1 +0 +1) = 0.
Input Format:
The first line contains an integer, ‘N’, representing the number of elements in the array.
The next line contains ‘N’ space-separated integers representing the elements of the array.
Output format:
Return an integer, the number of all the unique triplets with zero-sum.
Approaches
Approach:
The solution to the problem lies in first sorting the array, then we can apply the two pointers approach. The two pointers approach would be traversing the array from one side and then for the fixed element we can find other two elements using two pointers approach as the array is sorted now.
The steps are as follows:
Function [][int] triplet( int ‘N’, [int] ‘ARR’ )
- Sort the array ARR.
- Create a 2D array ‘ans’ to store all the triplets.
- For loop ‘idx’ in range 0 to N-3.
- If idx equal to 0 or ARR at (idx-1) and ARR at idx are not equal.
- Set left = idx+1, right = N-1 and sum as -ARR[idx].
- while(left < right)
- If ARR at left + ARR at right equal to sum.
- Push ARR at idx, left and right into the ans.
- While left < right and ARR at left and left+1 are equal.
- Increase left.
- While left < right and ARR at right and right-1 are equal.
- Decrease right.
- Increase left by 1 and decrease right by 1.
- Else if sum of ARR at left and right is less than sum.
- Increase left by 1.
- Else
- Decrease right by 1.
- If ARR at left + ARR at right equal to sum.
- If idx equal to 0 or ARR at (idx-1) and ARR at idx are not equal.
- Return ans.