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!

SPOJ: SUBSUMS - Subset Sums

Today I solved the Subset Sums (SUBSUMS) problem on SPOJ. Here's the link: http://www.spoj.com/problems/SUBSUMS

By the name of it, it seems like a classic Dynamic Programming problem, but as soon as you pay attention to the constraints, it soon becomes evident that a DP solution which will most optimally have O(N*W) complexity, where N = number of elements and W= the target sum range's upper bound, will bottleneck at W.

I solved this problem using Meet in the middle technique whereby, I divide the set of input numbers into 2 halves and consider sums of all subsets in each half (cardinality 2^17 in each set, which can be pretty easily generated using brute-force recursion), to find the subset-duos (containing one subset from each half) who sum up to fall in the given range. The count of such possible subset-duos gives us our solution. My solution also involves putting binary search and recursion into use.

Here's my accepted(https://www.spoj.com/status/SUBSUMS,chandniverma/) solution code:

  

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.function.BiPredicate;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		int arr[] = new int[N];
		for (int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		sc.close();
		
		System.out.println(getCountOfSubsets(arr, A, B));
	}

	private static long getCountOfSubsets(int[] arr, int a, int b) {
		Integer[] firstSubsetSums = getSubsetSums(arr, 0, arr.length/2);
		Integer[] secondSubsetSums = getSubsetSums(arr, arr.length/2+1, arr.length-1);
		Arrays.sort(secondSubsetSums);
		
		long count = 0;
		for(int i=0; i<firstSubsetSums.length; i++) {
			int p = findLastIdxWithFalsePredicate(secondSubsetSums, a-firstSubsetSums[i], (sum, mark)->sum>=mark);
			int q = findLastIdxWithFalsePredicate(secondSubsetSums, b-firstSubsetSums[i], (sum, mark)->sum>mark);
			count += (q-p);
		}
		
		return count;
	}

	private static int findLastIdxWithFalsePredicate(Integer[] sums, int val, BiPredicate<Integer, Integer> pred) {
		int min = 0;
		int max = sums.length-1;
		while (min<max) {
			int mid = min + (max-min+1)/2;
			if (pred.test(sums[mid], val)) {
				max = mid-1;
			} else {
				min = mid;
			}
		}
		if (pred.test(sums[min], val))
			return -1;
		return min;
	}

	private static Integer[] getSubsetSums(int[] arr, int st, int end) {
		List<Integer> sums = new ArrayList<>();
		generateSubsetSumsRecur(arr, st, end, st, 0, sums);
		return sums.toArray(new Integer[0]);
	}

	private static void generateSubsetSumsRecur(int[] arr, int st, int end, int index, int runningSum, List<Integer> sums) {
		if (index == end+1) {
			sums.add(runningSum);
			return;
		}
		
		generateSubsetSumsRecur(arr, st, end, index+1, runningSum+arr[index], sums);
		generateSubsetSumsRecur(arr, st, end, index+1, runningSum, sums);
	}
}

 
  

The complexity of the above code is:

O(2^(N/2) + 2^(N/2)*(lg (2^(N/2)))) 

= O(2^(N/2) + 2^(N/2)*N/2) 

= O(N*2^(N/2)) 

Feel free to checkout and let me know your thoughts in the comments below! Do share if you have a better solution in mind!