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