LeetCode Medium: 3Sum

Here I am sharing a solution to the Medium level LeetCode Problem of 3Sum: (https://leetcode.com/problems/3sum/).

 

The constraints about ensuring uniqueness of the triplets in the solution set make the problem all the more tricky as trying to do that using sorting or any other way would time out!

 

So, here I did the following:

 

1. Sort - O(n lg n)
2. For every element i, with arr[i] fixed as one of the triplets, perform TwoSum on the remainder of the following array - n* O(n) = O(n^2)
   (Where TwoSum can be efficiently done in O(n) time. Check this out: https://chandniverma.blogspot.com/2020/08/leetcode-easy-two-sum.html)

class Solution {
    public List> threeSum(int[] nums) {
        Arrays.sort(nums);
        List> result = new LinkedList<>();
        
        if (nums.length < 3)
            return result;
        
        for(int i=0; i < nums.length-2; i++) {
            
            // if(nums[i+1] == nums[i])
            //     continue; //bypass duplicate elements for first triplet
            
            // only first of repeated elements should be continued, to allow for repetition in triplet elements
            if(i==0 || (i>0 && (nums[i] != nums[i-1]))) {
            
                int sum = 0-nums[i];
                int low = i+1;
                int high = nums.length-1;

                //Do 2Sum on following subarray
                while (low < high) {
                    if (nums[low] + nums[high] == sum) {
                        //add validated triplet
                        result.add(Arrays.asList(nums[i], nums[low], nums[high]));
                        //skip duplicate occurrences of the above valid pair of elements our triplet
                        while(low < high && nums[low+1] == nums[low])
                            low++;
                        while(low < high && nums[high-1] == nums[high])
                            high--;
                        low++;
                        high--;
                    } else if ((nums[low] + nums[high]) > sum) {
                        high--;
                    } else {
                        low++;
                    }
                }
            }
            
        }
        
        return result;
    }
}

 

That;s all about it! See ya next time!