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.