Three Sum

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
198 upvotes
Asked in company
Dell Technologies

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
5 
-1 -1 2 0 1
Sample Output 1 :
-1 -1 2
-1 0 1
Explanation Of Sample Input 1:
(-1 -1 +2) = (-1 +0 +1) = 0.
Sample Input 2:
4 
0 0 0 0
Sample Output 2 :
0 0 0
Constraints:
1  <= N <= 1000
1 <= ARR[i] <= 1000
Time Limit: 1 sec
Hint

Try the problem after sorting the given array.

Approaches (1)
Two Pointers

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

  1. Sort the array ARR.
  2. Create a 2D array ‘ans’ to store all the triplets.
  3. 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.
  4. Return ans.
Time Complexity

O( N * N ), Where N is the size of the array. 

For the worst case, we are iterating all the elements once in the outer loop, then we are using the two-pointers approach inside the loop.

Hence the time complexity is O( N * N ).

Space Complexity

O(K * 3), Where K is the number of unique triplets.

We are using space for storing all the triplets.

Hence the space complexity is O(K * 3).

Code Solution
(100% EXP penalty)
Three Sum
Full screen
Console