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!

LeetCode Easy: Two Sum

Simple single pass O(n) solution to the Two Sum problem of LeetCode (https://leetcode.com/problems/two-sum/):

 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hm = new HashMap<>();
        
        
        for (int i=0; i<nums.length; i++) {
            if (hm.get(target - nums[i]) != null) {
                return (new int[]{hm.get(target - nums[i]), i});
            }
            hm.put(nums[i], i);
        }
        
        //never occours for appropriate inputs
        return new int[2];
    }
}

 

One can also solve the same by keeping two-pointers at the boundaries of the sorted version of the input array and either reducing the larger index inwards if the sum needed is lesser than the sum of the elements at the pointed indexes or incrementing the lower pointer index if the sum needed is larger than that of the current elements under the pointers, all while lesser pointed index <larger pointed index. If the input array is sorted, this will definitely be an optimization to the aformentioned O(n) solution! Otherwise, the sort will bottleneck the performance of this solution to O(n lg n).

 

Do share better ideas for solving this, that cross your mind!

 

Cheers!!

<3