LeetCode Easy(medium-ish): Subtree of Another Tree

Hello Peeps,

We're getting back in touch with problem solving after a long-long time. I was _really really_ busy with family functions in this break.

Yesterday, I solved this LeetCode problem Subtree of Another Tree categorised as easy on LeetCode. I would say medium would have been a more appropriate categorisation of this recursively solvable problem.

Problem link: https://leetcode.com/problems/subtree-of-another-tree/

Solution Approach: Recursion

Time Complexity: O(n) where n is the number of nodes in the tree s.

Space Complexity: O(h) where h is the height of the tree s.

Solution:

/**
 * 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 boolean isSubtree(TreeNode s, TreeNode t) {
        
        //Main logic
        boolean matchFound = false;
        
        //Base condition
        if (s == null && t == null)
            return true;

        if ((s!=null && t==null) || (s==null && t!=null))
            return false;

        if (s.val == t.val)
            matchFound = matches (s, t);

        if (!matchFound) {
            matchFound = isSubtree(s.left, t);
        }
        if (!matchFound) {
            matchFound = isSubtree(s.right, t);
        }

        return matchFound;
    }
    
    private boolean matches (TreeNode s, TreeNode t) {
        if (s==null && t==null)
            return true;
        if ((s!=null && t==null) || (s==null && t!=null))
            return false;
        if (s.val != t.val)
            return false;
        return matches(s.left, t.left) && matches(s.right, t.right);
    }
}

That's all for now!

Happy Coding!!

LeetCode Medium: Maximum Number of Vowels in a Substring of Given Length

Hello All,

 

Today’s coding problem is a Medium level LeetCode problem. Problem #1456: Maximum Number of Vowels in a Substring of Given Length

Link to Problem: https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

Problem Approach: Sliding Window

Time Complexity: O(n) where n is the number of characters in the input string.

Space Complexity: O(1) extra space

 

 

Accepted Java solution using Sliding Window:

 

class Solution {
    public int maxVowels(String s, int k) {
        if (s==null || s.length()<k) {
            return 0;
        }
        
        int maxVowelCnt = 0;
        int currentVowelCnt = 0;
        for (int i=0; i<=s.length()-k; i++) {
            if (i==0) { //1st window only
                for (int j=i; j<i+k; j++) {
                    if (isVowel(s.charAt(j)))
                        currentVowelCnt++;
                }
            } else { //remaining windows
                if(isVowel(s.charAt(i+k-1)))
                    currentVowelCnt++;
                if(isVowel(s.charAt(i-1)))
                    currentVowelCnt--;
            }
            
            maxVowelCnt = Math.max(maxVowelCnt, currentVowelCnt);
        }
        
        return maxVowelCnt;
    }
    
    private boolean isVowel(char c) {
        return c=='a' || c=='e' || c=='i' || c=='o' || c=='u' ;
    }
}

 

Video Explanation:

 

 

 

Share your thoughts!

Happy Coding!

 

 

Become a Patron!

 

LeetCode Hard: Find Median from Data Stream

LeetCode Problem #295: Find Median from Data Stream
Link to Problem Description: https://leetcode.com/problems/find-median-from-data-stream/
Category: Applications of Binary Heaps (or Priority Queues)
Solution Approach: Divide elements into 2 mutually-balanced Priority Queues - one having elements smaller than the middle element(s), one having larger.
Time Complexity of Approach:

• O(lg n) for insertion where n = number of elements seen so far.
• O(n) for finding the median of elements seen so far. Space Complexity: O(n) 

 

This LeetCode Hard Problem is a pretty neat application of Binary Heaps, which are readily usable as PriorityQueues in Java.

I have discussed the possible approaches to dolve the problem in the adjoining youtube video link and in this blog post I present 2 solutions for the Twin-heap based solution:

 

Approach #1: Using PriorityQueue Collection Class of Java Collections Framework

 

 

class MedianFinder {

    PriorityQueue lesser;
    PriorityQueue greater;
    
    public MedianFinder() {
        lesser = new PriorityQueue<>(10, (o1, o2)->o2-o1);
        greater = new PriorityQueue<>();
    }
    
    public void addNum(int num) { // O(lg n)
        if (lesser.size() == 0 || num < lesser.peek()) {
            lesser.add(num);
        } else {
            greater.add(num);
        }
        
        //Balance the heaps
        if (Math.abs(lesser.size() - greater.size()) <= 1)
            return;
        
        if (lesser.size() < greater.size())
            lesser.add(greater.poll());
        else
            greater.add(lesser.poll());
    }
    
    public double findMedian() { // O(1)
        if (lesser.size() == greater.size())
            return ((double)lesser.peek() + greater.peek())/2;
        
        if (lesser.size() > greater.size())
            return lesser.peek();
        return greater.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

 

 

Approach 2: Without using pre-build classes of Java - To test if you can code a Binary Heap data structure from scratch!

 

 

class MyPriorityQueue> {
    private ArrayList q;
    private Comparator comp;
    
    public MyPriorityQueue(int initialCapacity, Comparator cmp) {
        q = new ArrayList(initialCapacity);
        comp = cmp;
    }
    public MyPriorityQueue() {
        q = new ArrayList(10);
        comp = (o1, o2)->o1.compareTo(o2);
    }
    
    private int parent(int idx) {
        int pos = idx+1;
        return pos/2 - 1;
    }
    private int left(int idx) {
        int pos = idx+1;
        return (pos*2) -1;
    }
    private int right(int idx) {
        int pos = idx+1;
        return (pos*2+1) -1;
    }
    
    public void add (E e) {
        q.add(e);
        
        //bubble-up if necessary
        int currentIdx = q.size()-1;
        int parentIdx = parent(currentIdx);
        while (parentIdx >= 0 && comp.compare(e, q.get(parentIdx)) < 0) {
            q.set(currentIdx, q.get(parentIdx));
            q.set(parentIdx, e);
            currentIdx = parentIdx;
            parentIdx = parent(currentIdx);
        }
    }
    
    public int size() {
        return q.size();
    }
    
    public E peek() {
        if (q.isEmpty())
            return null;
        return q.get(0);
    }
    
    public void remove() {
        if (q.isEmpty())
            return;
        q.set(0, q.get(q.size()-1));
        q.remove(q.size()-1);
        minHeapify(0);
    }
    
    private void minHeapify(int i) {
        if (i >= q.size())
            return;
        
        int leastValIdx = i;
        if (left(i) < q.size() && comp.compare(q.get(leastValIdx), q.get(left(i))) > 0)
            leastValIdx = left(i);
        if (right(i) < q.size() && comp.compare(q.get(leastValIdx), q.get(right(i))) > 0)
            leastValIdx = right(i);
        
        if (leastValIdx != i) {
            E tmp = q.get(leastValIdx);
            q.set(leastValIdx, q.get(i));
            q.set(i, tmp);
            
            minHeapify(leastValIdx);
        }
    }
}

class MedianFinder {

    /** initialize your data structure here. */
    MyPriorityQueue lesserElementsMaxHeap;
    MyPriorityQueue greaterElementsMinHeap;
    
    public MedianFinder() {
        lesserElementsMaxHeap = new MyPriorityQueue<>(10, (o1, o2)->o2-o1);
        greaterElementsMinHeap = new MyPriorityQueue<>(); //minHeap by default
    }
    
    public void addNum(int num) {
        Integer lesserMax = lesserElementsMaxHeap.peek();
        if (lesserMax == null || lesserMax>num)
            lesserElementsMaxHeap.add(num);
        else
            greaterElementsMinHeap.add(num);
        
        
        //ensure balanced heaps
        if (Math.abs(lesserElementsMaxHeap.size() - greaterElementsMinHeap.size()) <= 1)
            return;
        
        if (lesserElementsMaxHeap.size() > greaterElementsMinHeap.size()) {
            lesserMax = lesserElementsMaxHeap.peek();
            greaterElementsMinHeap.add(lesserMax);
            lesserElementsMaxHeap.remove();
        } else {
            Integer greaterMin = greaterElementsMinHeap.peek();
            lesserElementsMaxHeap.add(greaterMin);
            greaterElementsMinHeap.remove();
        }
            
    }
    
    public double findMedian() {
        if (lesserElementsMaxHeap.size() == greaterElementsMinHeap.size())
            return ((double)lesserElementsMaxHeap.peek() + greaterElementsMinHeap.peek())/2;
        
        if (lesserElementsMaxHeap.size() > greaterElementsMinHeap.size())
            return lesserElementsMaxHeap.peek();
        else
            return greaterElementsMinHeap.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

 

 

 Video explanation for the approach:

 

 

Share your thoughts in comments!

 

<3

Become a Patron!

 

LeetCode Medium: Fruit Into Baskets

Y'day I solved LeetCode medium level problem: #904: Fruit Into Baskets ()

A quick heuristics-based solution with O(n) time-complexity in Java, which has been accepted by the LeetCode judge, is :

  
  class Solution {
    public int totalFruit(int[] tree) {
        Integer[] uniqueTreeTypesIdx = new Integer[2];
        uniqueTreeTypesIdx[0] = 0;
        
        int start = 0;
        int lastConsecutiveStretchStart = 0;
        int maxStretchLength = 1;
        int i = 1; //index counter
        for (i=1; i<tree.length; i++) {
            if (tree[i] != tree[uniqueTreeTypesIdx[0]]) {
                if (uniqueTreeTypesIdx[1] == null) {
                    uniqueTreeTypesIdx[1] = i;
                    lastConsecutiveStretchStart = i;
                } else if (tree[i] != tree[uniqueTreeTypesIdx[1]]) {
                    maxStretchLength = Math.max (maxStretchLength, i-1-start+1);
                    start = lastConsecutiveStretchStart;
                    uniqueTreeTypesIdx[0] = lastConsecutiveStretchStart;
                    uniqueTreeTypesIdx[1] = i;
                    lastConsecutiveStretchStart = i;
                } else { //tree[i] != tree[uniqueTreeTypesIdx[0]] && tree[i] == tree[uniqueTreeTypesIdx[1]] 
                    if (tree[i] == tree[lastConsecutiveStretchStart])
                        ;
                    else
                        lastConsecutiveStretchStart = i;
                }
            } else {
                if (tree[i] == tree[lastConsecutiveStretchStart])
                    ;
                else
                    lastConsecutiveStretchStart = i;
            }
        }
        maxStretchLength = Math.max (maxStretchLength, i-1-start+1);
        return maxStretchLength;
    }
}
  

I would like to re-visit it in near-times, to devise a more elegant and intuitive solution approach, but this is it for now!

Stay tuned for the next one!

Become a Patron!

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!

SPOJ Dynamic Programming: KNAPSACK

Today I started with solving Dynamic Programming problems and the first one on the refresher list was the classical 0/1-Knapsack.

I found an online judge, SPOJ, testing solutions to this problem here: https://www.spoj.com/problems/KNAPSACK/

Here is my accepted(https://www.spoj.com/status/KNAPSACK,chandniverma/) solution to the same:

import java.util.*;
import java.lang.*;

class Main
{
 public static void main (String[] args) throws java.lang.Exception
 {
  Scanner sc = new Scanner (System.in);
  int s = sc.nextInt();
  int n = sc.nextInt();
  
  int[] size = new int[n+1];
  long[] val = new long[n+1];
  for (int i=1; i<=n; i++) {
   size[i] = sc.nextInt();
   val[i] = sc.nextInt();
  }
  sc.close();
  
  long[][] memo = new long[n+1][s+1];
  for (int i=0; i<=n; i++) {
   for (int j=0; j<=s; j++) {
    memo[i][j] = -1;
   }
  }
  System.out.println(getMaxVal(size, val, s, n, memo));
 }

 private static long getMaxVal(int[] size, long[] val, int s, int n, long[][] memo) {
  if (n<=0 || s<=0)
   return 0;

  if (memo[n][s] != -1)
   return memo[n][s];

  if ((s-size[n]) >= 0) {
   return memo[n][s] = Math.max (
    val[n] + getMaxVal(size, val, s-size[n], n-1, memo),
    getMaxVal(size, val, s, n-1, memo)
    );
  } else {
   return memo[n][s] = getMaxVal(size, val, s, n-1, memo);
  }
 }
}

This solution works with a complexity of O(n*s) where n is the number of items under consideration and s is the size or capacity of the bag.

You can always find my SPOJ profile with solved problem list at https://www.spoj.com/users/chandniverma/.

You can also checkout my recent-most submissions at SPOJ on https://www.spoj.com/status/chandniverma/.

Feel free to share optimisations and improvisations in comments below!

See ya next time!

<3✌

LeetCode Medium: Count Complete Tree Nodes

Here is one LeetCode Medium level problem (Problem # 222: Count Complete Tree Nodes) which is an actual 2 liner to solve when solved recursively:

/**
 * 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 int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

This solution is O(n) in number of nodes in the binary tree and is a generic solution that can be used to solve any binary tree for that matter.

The fact that this is a complete binary tree, brings to my mind another solution approach with O((lg n)^2) solution which I'll share here very soon!

Until next time,

Stay Tuned and Happy Coding!

See ya later!!

LeetCode Problem #441. Arranging Coins

Here is my solution on LeetCode Problem #441. Arranging Coins 

Approach 1: Based on binary search and inequalities

class Solution {
    public int arrangeCoins(int N) {
        long minLevel = 0;
        long maxLevel = N;
        while (minLevel<maxLevel) {
            long midLevel = minLevel + (maxLevel-minLevel+1)/2;
            boolean predicate = ((midLevel*midLevel + midLevel) > (2*(long)N));
            
            if (predicate) {
                maxLevel = midLevel-1;
            }
            else {
                minLevel = midLevel;
            }
        }
        
        if ((minLevel*minLevel + minLevel) > (2*(long)N))
            return -1;
        return (int)minLevel;
    }
}

The time complexity is super-fast: O(lg n) where n is the the input N(the number of coins) and I don't think it can get any faster iteratively.

The only other faster solution I can think of is using SriDharacharya formula to find the roots to inequality:

l^2 + l <= 2*N

where l = last complete level

Do share your thoughts below!

<3
~Take Care

LeetCode Medium: Lowest Common Ancestor of a Binary Tree

My Solution for LeetCode medium problem #236: Lowest Common Ancestor of a Binary Tree, based on tree-recursion:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        boolean leftHasP = hasDescendant(root.left, p.val);
        boolean leftHasQ = hasDescendant(root.left, q.val);
        boolean rightHasP = hasDescendant(root.right, p.val);
        boolean rightHasQ = hasDescendant(root.right, q.val);
        
        if (root.val == p.val || root.val == q.val)
            return root;
        if ((leftHasP && rightHasQ) || (leftHasQ && rightHasP))
            return root;
        if (!leftHasP && !leftHasQ)
            return lowestCommonAncestor(root.right, p, q);
        else
            return lowestCommonAncestor(root.left, p, q);
        
    }
    
    private boolean hasDescendant(TreeNode root, int val) {
        if (root == null)
            return false;
        
        if (root.val == val) {
            return true;
        }
        if (hasDescendant(root.left, val) || hasDescendant(root.right, val)) {
            return true;
        }
        
        return false;
    }
}

Feel free to share your thoughts in comments, below!

LeetCode Medium: Construct Binary Tree from Inorder and Postorder Traversal

When we are given Inorder traversal of nodes in a tree, along with 1 other traversal, either preorder or postorder,  we can derive the original tree structure from the provided information.

I have solved the following LeetCode problem with the same idea in mind. Grab a look:

Problem #106: Construct Binary Tree from Inorder and Postorder Traversal 

/**
 * 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 TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length==0)
            return null;
        TreeNode root = treeFromInorderPostorder(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
        return root;
    }
    
    private TreeNode treeFromInorderPostorder(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        
        int inRootIdx = inStart;
        for (int i=inStart; i<=inEnd; i++) {
            if (inorder[i]==rootVal) {
                inRootIdx = i;
                break;
            }
        }
        // assert(inRootIdx != -1);
        int nodesInLeftSubtree = inRootIdx - inStart;
        if (nodesInLeftSubtree == 0) {
            root.left = null;
        } else {
        root.left = treeFromInorderPostorder(inorder, inStart, inRootIdx-1, postorder, postStart, postStart+nodesInLeftSubtree-1);
        }
        
        int nodesInRightSubtree = inEnd - inRootIdx;
        if (nodesInRightSubtree == 0) {
            root.right = null;
        } else {
        root.right = treeFromInorderPostorder(inorder, inRootIdx+1, inEnd, postorder, postStart+nodesInLeftSubtree, postEnd-1);
        }
        
        return root;
    }
}

In the similar vein, consider a previously solved problem:

Problem #105: Construct Binary Tree from Preorder and Inorder Traversal

The bounds for parameters with which to make recursive calls in these problems can be slightly tricky to understand so one needs to be careful with those.

Besides that, as always, let me know in comments if you find these solutions helpful or have ideas for improvement.

Toodles!

LeetCode medium: Construct Binary Tree from Preorder and Inorder Traversal

When we are given Inorder traversal of nodes in a tree, along with 1 other traversal, either preorder or postorder,  we can derive the original tree structure from the provided information.

I have solved the following LeetCode problem with the same idea in mind:

Problem #105: LeetCode medium: Construct Binary Tree from Preorder and Inorder Traversal

/**
 * 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 TreeNode buildTree(int[] preorder, int[] inorder) {
        if (inorder.length == 0 || preorder.length==0)
            return null;
        TreeNode root = treeFromInorderPreorder(inorder, 0, inorder.length-1, preorder, 0, preorder.length-1);
        return root;
    }
    
    private TreeNode treeFromInorderPreorder(int[] inorder, int inStart, int inEnd, int[] preorder, int preStart, int preEnd) {
        
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        
        int inRootIdx = inStart;
        for (int i=inStart; i<=inEnd; i++) {
            if (inorder[i]==rootVal) {
                inRootIdx = i;
                break;
            }
        }
        // assert(inRootIdx != -1);
        int nodesInLeftSubtree = inRootIdx - inStart;
        if (nodesInLeftSubtree == 0) {
            root.left = null;
        } else {
        root.left = treeFromInorderPreorder(inorder, inStart, inRootIdx-1, preorder, preStart+1, preStart+1+nodesInLeftSubtree);
        }
        
        int nodesInRightSubtree = inEnd - inRootIdx;
        if (nodesInRightSubtree == 0) {
            root.right = null;
        } else {
        root.right = treeFromInorderPreorder(inorder, inRootIdx+1, inEnd, preorder, preStart+nodesInLeftSubtree+1, preEnd);
        }
        
        return root;
    }
}

In the similar vein, consider:

Problem #106: Construct Binary Tree from Inorder and Postorder Traversal

The bounds for parameters with which to make recursive calls can be slightly tricky to understand so one needs to be careful with those.

Besides that, as always, let me know in comments if you find these solutions helpful or have ideas for improvement.

Toodles!...

LeetCode Medium: Binary Tree Level Order Traversal

Here is my solution to LeetCode Problem #102: Binary Tree Level Order Traversal based on BFS traversal with modification -

/**
 * 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<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()) {
            int levelSize = q.size();
            List<Integer> level = new ArrayList<> ();
            for (int i=0; i<levelSize; i++) {
                TreeNode current = q.remove();
                level.add(current.val);
                if (current.left != null) q.add(current.left);
                if (current.right != null) q.add(current.right);
            }
            res.add(level);
        }
        
        return res;
    }
}

Try these related problems too:

https://chandniverma.blogspot.com/2020/06/leetcode-medium-binary-tree-right-side.html

LeetCode: More problems on Trees

Here are my Java solutions to more problems on trees. Following are 2 related ones:

Problem #104: Maximum Depth of Binary Tree

/**
 * 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 int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        
        int lDepth = maxDepth(root.left);
        int rDepth = maxDepth(root.right);
        
        return Math.max(lDepth, rDepth)+1;
    }
}

Problem #543: Diameter of a Binary Tree

/**
 * 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 {
    
    private int height(TreeNode root) {
        if (root == null)
            return -1;
        
        return Math.max(height(root.left), height(root.right)) + 1;
    }
    
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null)
            return 0;
        
        int lHeight = height(root.left);
        int rHeight = height(root.right);
        int lDiameter = diameterOfBinaryTree(root.left);
        int rDiameter = diameterOfBinaryTree(root.right);
        
        return Math.max(lHeight+rHeight+2 , Math.max(lDiameter, rDiameter));
    }
}

~~~

I plan to extend this category of posts with more related ones to come soon!

Until then,

Happy Problem Solving!!

LeetCode Trees and Graphs: Problem #101: Symmetric Tree

The next problem on hit list is Problem #101: Symmetric Tree

Again, this can be solved using many approaches both recursively or iteratively.

Approach 1: My recursive solution with complexity O(n) where n is the total number of TreeNodes in the tree is as follows:

/**
 * 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 boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        
        if (root.left == null && root.right == null)
            return true;
        
        return isMirror (root.left, root.right);
    }
    
    private boolean isMirror(TreeNode r1, TreeNode r2) {
        if (r1 == null && r2 == null)
            return true;
        if ((r1 == null && r2 != null) || (r1 != null && r2 == null))
            return false;
        if (r1.val != r2.val)
            return false;
        
        boolean mirror = isMirror(r1.left, r2.right);
        if (mirror)
            mirror = isMirror(r1.right, r2.left);
        
        return mirror;
    }
}

Approach 2: An iterative solution approach making use of a BFS like queue insertion of node-pairs to check for equality when popped (again O(n)):

/**
 * 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 boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        
        if (root.left == null && root.right == null)
            return true;
        
        //iterative solution
        
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root.left);
        q.add(root.right);
        while(!q.isEmpty()) {
            TreeNode n1 = q.remove();
            TreeNode n2 = q.remove();
            
            if (n1 == null && n2 == null)
                continue;
            if ((n1 == null && n2 != null) || (n1 != null && n2 == null))
                return false;
            if (n1.val != n2.val)
                return false;
            
            q.add(n1.left);
            q.add(n2.right);
            q.add(n1.right);
            q.add(n2.left);
        }
        
        return true;
    }
}

That's not all! There are definitely more approaches to it. One which I can think of is using stacks. Feel free to share your solutions for the same.

As always, you can checkout my latest accepted solutions on leetcode at https://leetcode.com/chandniverma/ . All the best!

LeetCode Trees and Graphs: Problem #100: Same Tree

Today I plan to do some problems on trees. With that, I started with Same Tree.

Here's my recursive solution of the same:

/**
 * 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 boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null) {
            if (q == null)
                return true;
            return false;
        } else {
            if (q == null)
                return false;
        }
        
        if (p.val != q.val)
            return false;
        
        boolean sameTree = true;
        sameTree = isSameTree(p.left, q.left);
        
        if (sameTree)
            sameTree = isSameTree(p.right, q.right);
        
        return sameTree;
    }
}

Sweet and Simple!

Happy Coding!!

LeetCode Hard: Merge k sorted Lists

I just solved LeetCode hard problem #23: Merge k sorted Lists, which is asked in interviews for a lot of companies, including Facebook, Uber, Google and you name it! It can look intimidating but...

Hint: It's too easy if you can think of the right Data Structure for solving the problem.

Here's my O(lg n) solution where n is the cardinality of all the elements combined in all lists:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(-1);
        
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for(ListNode list : lists) {
            while (list != null) {
                minHeap.add(list.val);
                list = list.next;
            }
        }
        
        ListNode head = dummy;
        while (!minHeap.isEmpty()) {
            head.next = new ListNode(minHeap.remove());
            head = head.next;
        }
        
        return dummy.next;
    }
}

Feel free to share your thoughts below!

LeetCode Medium: Binary Tree Postorder Traversal | T-Contest: Minimal Source Call for Submissions

My recursive solution for Problem #145: Binary Tree Postorder Traversal:

/**
 * 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<Integer> postorderTraversal(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        postorderTraversalRecur(root, values);
        return values;
    }
    
    void postorderTraversalRecur(TreeNode root, List<Integer> values) {
        if (root == null)
            return;
        
        postorderTraversalRecur(root.left, values);
        postorderTraversalRecur(root.right, values);
        values.add(root.val);
    }
}

I leave the iterative one for you to do as an exercise!

Let's see some solutions coming up through the remainder of June and July 2020, and the Java solution with least program-size(size of source code) will win a free t-shirt from Let's Code_ merchandise!!!

Let's Code_!!!

Earned Udemy Course Completion Certification for "Learn Java Unit Testing with JUnit 5 in 20 Steps"

Its an amazing feeling to have your skills acknowledged, enhanced and certified by the Bestselling instructor on Udemy, Mr. Ranga Karanam himself!

I'm glad to share that today, I successfully completed the course on "Learn Java Unit Testing with JUnit 5 in 20 Steps" and earned certification of successful completion for the same: https://www.udemy.com/certificate/UC-fc967ea9-ee3f-4873-9ccc-4b40a11f62d1/

Thank you Udemy!
A big Thank You Mr. Ranga Karanam for such concise, simplified yet precise administration of the course!

LeetCode Medium: Binary Tree Inorder Traversal

Here are 2 of my accepted solution approaches (both O(n) where n is the number of nodes in the input tree) for solving the Problem #94 Binary Tree Inorder Traversal on Leetcode:

Approach 1: Simple Recursive

/**
 * 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<Integer> preorderTraversal(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        preorderTraversalRecur(root, values);
        return values;
    }
    
    void preorderTraversalRecur(TreeNode root, List<Integer> values) {
        if (root == null)
            return;
        
        values.add(root.val);
        preorderTraversalRecur(root.left, values);
        preorderTraversalRecur(root.right, values);
    }
}

Approach 2: Iterative Stack based

/**
 * 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<Integer> inorderTraversal(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        inorderTraversal(root, values);
        return values;
    }
    
    void inorderTraversal(TreeNode root, List<Integer> values) {
        if (root == null)
            return;
        
        inorderTraversal(root.left, values);
        values.add(root.val);
        inorderTraversal(root.right, values);
    }
}

Know of any more alternative? ..Feel free to share your code or suggestions in comments below!

LeetCode Medium: Binary Tree Preorder Traversal

Hello Fellas,

Here are 2 of my accepted solution approaches (both O(n) where n is the number of nodes in the input tree) for solving the Problem #144 Binary Tree Preorder Traversal on Leetcode:

Approach 1: Simple Recursive

/**
 * 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<Integer> preorderTraversal(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        preorderTraversalRecur(root, values);
        return values;
    }
    
    void preorderTraversalRecur(TreeNode root, List<Integer> values) {
        if (root == null)
            return;
        
        values.add(root.val);
        preorderTraversalRecur(root.left, values);
        preorderTraversalRecur(root.right, values);
    }
}

Approach 2: Iterative Stack based

/**
 * 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<Integer> preorderTraversal(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        if (root == null) 
            return values;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push (root);
        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            values.add(current.val);
            
            if (current.right != null)
                stack.push(current.right);
            if (current.left != null)
                stack.push(current.left);
        }
        
        return values;
    }
}

Know of more ways, feel free to share your code or suggestions in comments below!

LeetCode Medium: Binary Tree Right Side View

Today I solved the Leetcode medium problem #199 Binary Tree Right Side View. Here's the solution of the same using Level order Traversal while keeping a track of the last element on each level:

/**
 * 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<Integer> rightSideView(TreeNode root) {
        List<Integer> rightVisibleList = new ArrayList<> ();
        if (root == null)
            return rightVisibleList;
        
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i=0; i<size; i++) {
                TreeNode out = q.poll();
                if (i == size-1)
                    rightVisibleList.add(out.val);
                
                if (out.left != null)
                    q.add(out.left);
                
                if (out.right != null)
                    q.add(out.right);
            }
        }
        
        return rightVisibleList;
        
    }
}

In case we were to solve it for Left Side View we would have just kept a track of the first element at each level and that would have done the deal!

Happy Coding until next time!

LeetCode Medium: Kth Largest Element in an Array

My Solution to Leetcode Problem #215: Kth Largest Number in an Array.

This one's O(n lg k) based intuitively on a minHeap where n is the number of elements in nums and k is k which is usually much smaller than n.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int e: nums) {
            minHeap.add(e);
            if (minHeap.size()>k)
                minHeap.remove();
        }
        //Now minHeap contains largest k elements of all.
        return minHeap.remove();
        
    }
}

As a plus point, this code submitted by me works very well for unlimited amounts of streaming in data for an online algorithm too!

Were we to find the Kth Smallest element from an unsorted array, we would have used a maxHeap to store the smallest K of all the elements into it, evicting the maximum of them all every time the size of heap exeeded K.

In that case, we would have modified the PriorityQueue at creation time with a custom comparator using either of the following:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
queue.offer(1);


PriorityQueue<Integer> maxHeap =new PriorityQueue<>((x, y) -> Integer.compare(y, x));



Note that a lambda comparator like (x, y) -> y - x may be not appropriate for long integers due to overflow. For example, numbers y = Integer.MIN_VALUE and x = 5 results in positive number. It is better to use new PriorityQueue<>((x, y) -> Integer.compare(y, x)).

LeetCode Medium: Battleships in a Board

Following 2 approaches (at-least) can be used to solve Problem #419: Battleships in a Board:

Approach 1: O(n^2) DFS Sinking, where n is the number fo cells in the board

class Solution {
    public int countBattleships(char[][] board) {
        int battleships = 0;
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[i].length; j++) {
                if (board[i][j]=='X') {
                    battleships++;
                    sink(board, i, j);
                }
            }
        }
        return battleships;
    }
    
    void sink(char[][] board, int i, int j) {
        if (i<0 || i>=board.length || j<0 || j>=board[i].length || board[i][j]!='X') {
            return;
        }
        
        board[i][j] = '.';
        sink (board, i+1, j);
        sink (board, i-1, j);
        sink (board, i, j+1);
        sink (board, i, j-1);
    }
}

Approach 2: Single Pass O(n), by counting only the head Xs of every battleship

class Solution {
    public int countBattleships(char[][] board) {
        int battleships = 0;
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[i].length; j++) {
                if (board[i][j]=='.' || (i>0 && board[i-1][j]=='X') || (j>0 && board[i][j-1]=='X'))
                    continue;
                battleships++;
            }
        }
        return battleships;
    }
}

LeetCode Medium: Container with Most Water

Some time back, I revisited one of my previously solved LeetCode medium problems that had my upvote:

Problem #11: Container With Most Water

My original solution approach was as follows:

Approach 1:

class Solution {
 public int maxArea(int[] height) {
        ArrayList<Integer> highestRightmostIndexes = new ArrayList<> (height.length);
        for (int i=0; i<height.length-1; i++) {
            int maxRightIdx = i;
            for (int j=i+1; j<height.length; j++) {
                if (height[i]<=height[j])
                    maxRightIdx = j;
            }
            highestRightmostIndexes.add(maxRightIdx);
        }
        highestRightmostIndexes.add(0);
        
        ArrayList<Integer> highestLeftmostIndexes = new ArrayList<> (height.length);
        highestLeftmostIndexes.add(0);
        for (int i=1; i<height.length; i++) {
            int maxLeftIdx = i;
            for (int j=i-1; j>=0; j--) {
                if (height[i]<=height[j])
                    maxLeftIdx = j;
            }
            highestLeftmostIndexes.add(maxLeftIdx);
        }
        
        int resArea = 0;
        for(int i=0; i<height.length; i++) {
            resArea = Math.max(resArea, (Math.min(height[i], height[highestRightmostIndexes.get(i)])*Math.abs(i-highestRightmostIndexes.get(i))));
        }
        for(int i=0; i<height.length; i++) {
            resArea = Math.max(resArea, (Math.min(height[i], height[highestLeftmostIndexes.get(i)])*Math.abs(i-highestLeftmostIndexes.get(i))));
        }
        
        return resArea;
    }
}

As one can perceive, this was a tad lengthy and also less intutive.

Today I solved the same using the following 2 new approaches:

Approach 2: O(n^2) Brute Force

class Solution {
 public int maxArea(int[] height) {
     int maxArea = Integer.MIN_VALUE;
     for (int i=0; i<height.length; i++) {
         for (int j=i+1; j<height.length; j++) {
             int lesserHeight = Math.min(height[i], height[j]);
             maxArea = Math.max (maxArea, lesserHeight*(j-i));
         }
     }
     return maxArea;
 }
}

Approach 3: O(n) Single Pass using Two Pointers

class Solution {
 public int maxArea(int[] height) {
     int i = 0, j = height.length-1;
     
     int maxArea = Integer.MIN_VALUE;
     while (i<j) {
         int lesserHeight = Math.min(height[i], height[j]);
         maxArea = Math.max(maxArea, lesserHeight*(j-i));
         if (height[i]<height[j]) {
             i++;
         } else {
             j--;
         }
     }
     
     return maxArea;
 }
}

Do you know of any better approach? Let me know your thoughts in the comments below!

Leetcode Medium: Letter Combinations of a Phone Number

A few days back I coded a Leetcode medium problem: Letter Combinations of a Phone Number (problem #17) as follows:

import java.util.Hashtable;

class Solution {
    public List<String> letterCombinations(String digits) {
        ArrayDeque<String> res = new ArrayDeque<>();
        res.add("");
        
        Hashtable<Integer, String> ht = new Hashtable<>();
        ht.put(2, "abc");
        ht.put(3, "def");
        ht.put(4, "ghi");
        ht.put(5, "jkl");
        ht.put(6, "mno");
        ht.put(7, "pqrs");
        ht.put(8, "tuv");
        ht.put(9, "wxyz");
        
        letterCombinationsRecur(digits, 0, ht, res);
        return new ArrayList<String>(res);
    }
    
    private void letterCombinationsRecur(final String digits, int digPtr, final Hashtable<Integer, String> ht, final ArrayDeque<String> res) {
        
        if (digPtr==digits.length()) {
            if (res.peekFirst().equals(""))
                res.removeFirst();
            return;
        }
        
        int inputResCnt = res.size();
        ArrayList<String> resAL = new ArrayList<>(res);
        
        
        String newLastChars = ht.get(digits.charAt(digPtr) - '0');
        int nlcLen = newLastChars.length();
        for (int nlcIdx=0; nlcIdx<nlcLen; nlcIdx++) {
            
            for (int i=0; i<inputResCnt; i++) {
                res.add(resAL.get(i) + newLastChars.charAt(nlcIdx));
            }
            
        }
        
        for (int i=0; i<inputResCnt; i++) {
            res.removeFirst();
        }
        letterCombinationsRecur(digits, ++digPtr, ht, res);
        
    }
}

Today, I revisited that problem and thought I could use a simplified technique to solve the problem by modifying the above solution to rely less of Level Order BFS-like dequeue population and rely more over recursion. Here's the result that resultantly significantly simpler:

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0)
            return result;
        
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        letterCombinationsRecur (digits, 0, "", mapping, result);
        return result;
    }
    
    void letterCombinationsRecur (String digits, int digitPtr, String currentLetterCombination, String[] mapping, List<String> result) {
        if (digitPtr == digits.length()) {
            result.add(currentLetterCombination);
            return;
        }
        
        String currDigLetters = mapping[digits.charAt(digitPtr)-'0'];
        for (int i=0; i<currDigLetters.length(); i++) {
            letterCombinationsRecur(digits, digitPtr+1, currentLetterCombination+currDigLetters.charAt(i), mapping, result);
        }
    }
    
}

Let me know your thoughts in the comment section below! Meanwhile, happy coding!!

Leetcode Medium: Single Number II

Here's jot of my Leetcode submission in Java to "Single Number II" problem (problem #136) on leetcode.

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            hm.put(nums[i], hm.getOrDefault(nums[i], 0) + 1);
        }
        
        for (int key : hm.keySet()) {
            if (hm.get(key) == 1)
                return key;
        }
        
        return -1;
    }
}

As always you can track my recent-most submissions on my leetcode page: https://leetcode.com/chandniverma/

Feel free to share your thoughts in comments.

Leetcode Medium - Find Peak Element

Following is my Solution to Problem #162: Find Peak Element. Feel free to discuss and/or add your comments.

class Solution {
    public int findPeakElement(int[] nums) {
        
        if (nums.length ==1)
            return 0;
        
        for (int i=1; i<nums.length; i++)
            if (nums[i]<nums[i-1]) {
                return i-1;
            }
        
        return nums.length-1;
    }
}

There's a faster solution that guarantees answer in O(lg(n)) time. It uses Binary Search trick.

class Solution {
    public int findPeakElement(int[] nums) {
        
        if (nums.length ==1)
            return 0;
        
        int min = 0;
        int max = nums.length-1;
        while (min<max) {
            int mid = min+ (max-min)/2;
            
            if (nums[mid]<nums[mid+1])
                min = mid+1;
            else
                max = mid;
        }
        
        return min;
    }
}

Leetcode Medium - Number of Islands

Today, I started solving Leetcode medium questions.

For reference purpose, I'll be jotting down my solutions to these problems here.

Following is an accepted quick solution to the  Number of Islands problem (problem #200) on Leetcode. This solution implements it using the land "sinking" technique.

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length==0)
            return 0;
        
        int islands = 0;
        for (int i=0; i<grid.length; i++) {
            for (int j=0; j<grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    islands += dfs(grid, i, j);
                }
            }
        }
        return islands;
    }
    
    int dfs(char[][] grid, int i, int j) {
        if (i<0 || i>=grid.length || j<0 || j>=grid[i].length || grid[i][j]=='0') {
            return 0;
        }
        
        //sink
        grid[i][j] = '0';
        
        dfs(grid, i+1, j);
        dfs(grid, i, j+1);
        dfs(grid, i-1, j);
        dfs(grid, i, j-1);
        
        return 1;
        
    }
}

LeetCode Problems Asked At FAANG Interviews - Part 1

The world has seen a number of job cuts worldwide. Some of the software engineering workforce has quit their jobs by their own will.

In such trying times when all economies are dwindling, it is the chance for the workforce to instead of giving up, pause and introspect on their ideal next workplace, and give their best to come out of the lockdown with flying colours.

I am a Software Engineer myself and with the aim of providing a not so unconventional path to help other software engineers reach their similar goals, in the last 2-3 weeks of my free time I audited the frequently asked problems at one of the big gigs in the software industry, particularly focussing on Amazon, the 'A' of "FAANG"(Facebook, Amazon, Apple, Netflix and Google).

In this blogpost I have collated some of those problems asked at Amazon, which will be useful for anyone preparing for interviews at Amazon and also someone who is trying to just get started with interviewing in general.

Amazon Interview Questions solved and audited by me:

1. First Unique Character in a String
2. Single Number
3. Power of Two
4. Robot Return to Origin
5. Missing Number
6. Best Time to Buy and Sell Stock II
7. Path Sum
8. Letter Combinations of a phone
9. Remove Element
10. Climbing Stairs
11. Lowest Common Ancestor of BST
12. Jewels and Stones
13. Container with most water
14. First unique character in a string
15. Flood Fill
16. Reverse Linked List - Try Iterative and Recursive both
17. Most Common Word
18. Unique Email Addresses

My LeetCode profile is : https://leetcode.com/chandniverma/ for you to checkout!

I would encourage all those who are getting set for preparing them for interviews to go through these problems by their own and feel free to ask their questions and share their doubts with me to keep this discussion open-ended and the Let's Code_ problem solving community alive! As you would have seen, the problems asked at Amazon are fairly simple and most come under the easy category of problems on LeetCode so they are good for starters.

Mock-interviews go a long way to help judge your standing among peers and have helped me many times as well.

I particularly conduct and give interviews on PRAMP (www.pramp.com) an acronym for PRActice Makes Perfect, and if you ever need PRAMP credits to sharpen your skills, feel free to get in touch! Do ping me with your account and I'll be happy to share some with you.

Until then, Happy Coding!!

Lockdown and Upskilling Problem Solving

Being busy has never given anyone a chance to reflect and up-skill themselves.

One of the best things a programmer can do to up-skill their coding capabilities is to work on the Art of Problem Solving and becoming world-class in doing it.

Why not must one utilise the Lockdown period with up-skilling oneself using techniques outlined by veterans like the CCDSAP curriculum which is laid down as a guidance mechanism to gain control over exactly what you want - problem solving using programming!

With the same line of thought in mind, I have restarted my programming practice and I'll document for you, how I go about the curriculum as we progress through this blog!

There are a few other up-skilling sites I keep in touch with like spoj.com, leetcode.com and hackerrank.com and I'll blog about solving problems there as well.

So, Let's Code!!!

A Oneliner for grepping character-by-character differences between two files anywhere on filesystem

Long story short:

Install git.
Hit this at command-prompt from within any git repo(can create afreash using `git init`):

 git diff  --no-index --word-diff=color --word-diff-regex=. /path/to/file1 /path/to/file2

Sample Result:

Dear Cybernauts,

Many a times you might have wondered a way to compare 2 files not just word to word but character-by-character, nicely coloured, and easy to spot on minute changes!

Without finding anything easily on the Internet apart from purchasable solutions (such as desktop versions of diffchecker.com..) not worth the pennies, I dug up some manuals and found it worth the effort to document it for the lazyweb. There you go! ^^ 😉(HaCk tHe BuSy-NeSSeS build on top of it!??!!! Use the 'man' if needed!)


~Namaste
🙏