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!!

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: 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 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 - 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;
    }
}