Data Structures and Algorithms in Java – Arrays – Three sum

Problem:

Given an array of integers , find out triplets in the array such that their sum is 0.

Constraints:

There should not be any duplicates.

Same number should not be added to itself.

Assumptions:

The array contains a minimum of 3 elements and maximum 3000 elements

Numbers can vary from -100000 to 100000

Input:

[-1,0,1,2,-1,-4]

Output:

[[-1,-1,2],[-1,0,1]]

Try out the solution here:

3Sum – LeetCode

Solution:

The brute force solution for this problem is to iterate each element three times using three nested for loops. For each element you can add any one of the remaining elements and again to this sum you can add any one of the remaining elements. The time complexity is O(n³ ).

A better solution exists of time complexity O(n² ).

Hint:

• Sort the array to find out and remove duplicates.
• For each element in the array , use two pointers – a left pointer to the next element and a right pointer to the last element in the sorted array.
• Add those two elements with the original element and see if the sum is 0 , then add it to the output , if it is less than 0 increment the left pointer and if it is greater than 0 , decrement the right pointer

Example:

For example , consider the array

[-1,0,1,2,-1,4]

Sort this array first , which then becomes:

[-1,-1,0,1,2,4]

Now take the first element -1.

Have two pointers one pointing to the next element which is also -1 and one pointing to the last element which is 4.

Now add the original element , the next element and the last element:

-1+-1+4 = 2 , which is greater than 0.

Since we have the largest element at the last in a sorted array , moving to the previous element will reduce the sum and we might get 0, so move the last pointer to the previous element which is 2 now

[-1,-1,0,1,2,4]

-1+-1+2 = 0 , now the sum is 0.

We have got the first triplet [-1,-1,2] ,add that to output

Now let’s find the next triplet.

The original element is still the first element -1.

Let’s move the left pointer to the next position which points to 0 now.

Let’s add all the elements:

[-1,-1,0,1,2,4]

-1+0+2 = 1 , which is greater than 0

So lets decrement the last pointer.

The last pointer now points to 1:

[-1,-1,0,1,2,4]

The sum now is -1+0+1 = 0

We have got another triplet [-1,0,1] , add that to the output.

Now if you increment the left pointer it joins the right pointer , so don’t do it.

Go to the next element in the original array.

The next element in the original array is -1.

We already dealt with -1 , so it is going to give duplicate triplets.

So let’s ignore it and move on to the next element 0.

Again create two pointers one pointing to the next element of 0 which is 1 and another pointing to the last element which is 4.

Continue the same process until left pointer < right pointer.

During this proces,

There is a chance that the element next to the left pointer is also a duplicate.

In that case increment the left pointer so that you ignore the duplicate.

ALGORITHM:

STEP1: Sort the input array

STEP2: For each element in the sorted array

STEP2a: See if the element has already been processed , if yes ignore it and move to next

STEP2b: Create a pointer to the next element (left pointer)

STEP2c: Create a pointer to the last element (right pointer)

STEP2d: While the left pointer is less than the right pointer, find the sum of the original element , the left element and the right element

STEP2di: If the sum is 0, add that to the output , also check if the next element is the same as the left element , if so keep incrementing the left pointer till the next element is not equal to the left element , so that there are no duplicates.

STEP2dii: If the sum is less than 0, increment the left pointer

STEP2diii: If the sum is greater than 0 , increment the right pointer

Code:

Here is the code (with duplicate triplets):

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        
        
        var output = new ArrayList<List<Integer>>();
        
        
        
        Arrays.sort(nums);
        
        
        for(int i=0;i<nums.length;i++){
            
            
            int l = i+1;
            int r = nums.length -1;
            
            
            while(l < r){
                
               
                
                int sum = nums[i]+nums[l]+nums[r];
                
                
                if(sum < 0){
                    
                    l++;
                }else if(sum > 0){
                    
                    r--;
                }else{
                    
                    output.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    
                    l++;
                    
                
                }
                
              
                
            }
        }
        
        return output;
    }
}

Here is the code without the duplicates:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        
        
        var output = new ArrayList<List<Integer>>();
        
        
        
        Arrays.sort(nums);
        
        
        for(int i=0;i<nums.length;i++){
            
            
            
                
            while(i>0 &&  i < nums.length && nums[i]==nums[i-1]  ){
                
                i++;
            
            }
            
            int l = i+1;
            int r = nums.length -1;
            
            
            while(l < r){
                
               
                
                int sum = nums[i]+nums[l]+nums[r];
                
                
                if(sum < 0){
                    
                    l++;
                }else if(sum > 0){
                    
                    r--;
                }else{
                    
                    output.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    
                    l++;
                    
                     while(nums[l]==nums[l-1] && l < r){
                        l++;
                    }
                }
                
              
                
            }
        }
        
        return output;
    }
}

Time complexity:

We do sorting in the above algorithm , its time complexity is O(nlogn) (Java uses Quick Pivot sort internally)

Also there are two loops , one for loop and one while loop which makes the time complexity – O(n² ).

We can ignore O(nlogn) compared to O(n² ) , so time complexity is O(n² )

Space complexity is O(n) since duplicates are not allowed , you cannot have more than n triplets.

That’s it!