Announcement! Become our Patron!

 

Our very own Let’s Code_ community initiative is now having a Patreon Landing page! Just another way for you to say thanks!

 

Go: 

 

Become our Patron!

LeetCode Medium: Binary Tree Zigzag Level Order Traversal

My solution using BFS like- Level Order Traversal using Queue snapshots:

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List> zigzagLevelOrder(TreeNode root) {
        //BFS
        List<List> result = new LinkedList<>();
        if (root == null)
            return result;
        
        Queue q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int nextLevelSize = q.size();
            LinkedList level = new LinkedList<>();
            
            for (int i=0; i<nextLevelSize; i++) {
                TreeNode current = q.remove();
                
                if (result.size()%2 == 0) // level is an odd level to be added
                    level.add(current.val);
                else //even-level has elements added in reverse
                    level.addFirst(current.val);
                
                if (current.left != null)
                    q.add(current.left);
                if (current.right != null)
                    q.add(current.right);
            }
            
            result.add(level);
        }
        
        return result;
    }
}

 

Feel free to point out suggestions for improvement and share your outlook!

 

✌️

 

LeetCode Easy: Remove Duplicates from Sorted Array

An easy level problem on LeetCode - Remove Duplicates from Sorted Array (https://leetcode.com/problems/remove-duplicates-from-sorted-array/)

 

 

 

APPROACH 1:

 

I wrote a quick and easy solution in C++ for this easy level problem some years back - Single pass and O(n), ignoring all duplicates as we go:

class Solution {
public:
    int removeDuplicates(vector& nums) {
        int len = nums.size();
        if (len<=1)
            return len;
        
        int i, top;
        for (i=1, top=1; i<len; i++)
        {
            if (nums[i] != nums[top-1])
                nums[top++] = nums[i];
        }
        
        return top;
    }
};

 

 

 

APPROACH 2:

 

A couple of dys back, I revisited this problem, in Java, but this time, I looked at it and instantly came to my mind, an even more optimised version of it, O(lg m) in time complexity, where, m = number of unique elements in the input list, making use of predicate based binary searching technique to get the last occurrence of a particular element in the left part of the current index:

 

Here’s how the solution goes for it:

 

class Solution {
    public int removeDuplicates(int[] nums) {
        int reducedLen = -1;
        if (nums.length == 0)
            return reducedLen+1;
        
        int pos = 0;
        while (pos < nums.length) {
            pos = getLastOccurenceIdx(nums, pos);
            nums[++reducedLen] = nums[pos];
            pos++;
        }
        
        return reducedLen+1;
    }
    
    private int getLastOccurenceIdx(int[] nums, int firstPos) {
        int min = firstPos;
        int max = nums.length-1;
        while (min < max) {
            int mid = min + (max-min+1)/2;
            if (nums[mid]>nums[firstPos]) {
                max = mid-1;
            } else {
                min = mid;
            }
        }
        return min; 
    }
}

 

 

Do share if better solutions cross your mind!

Happy Coding, until next spree!!

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

LeetCode Hard: Special Binary String

This is one Hard category problem on LeetCode.

A few things to observe in this problem are :

1. Treating a special binary string as a string with 1 corresponding to char ‘(‘ and 0 to character ‘)’ reduces it to a valid string of properly closed parentheses.
2. The first character of special binary strings (like the input string) has to be a 1, and the last character, a 0.
3. The special binary string can be a concatenation of only special binary strings.

Keeping these factsin mind, here is my recursive solution to the same:

 

class Solution {
    public String makeLargestSpecial(String S) {
        
        ArrayList res = new ArrayList<>();
        
        int count = 0, st = 0;
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '1')
                count++;
            else
                count--;
            if (count == 0) {
                res.add('1' + makeLargestSpecial(S.substring(st+1, i)) + '0');
                st = i+1;
            }
        }
        
        Collections.sort(res, Collections.reverseOrder());
        return String.join("", res);
        
    }
}

Let me know your thouhts in the comments below.

 

Happy Coding!