Count Univalue Subtrees

Count Univalue Subtrees

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

return 4.

Solution:

public int countUnivalSubtrees(TreeNode root) {
    int[] count = new int[1];
    isUnivalSubtrees(root, count);
    return count[0];
}

public boolean isUnivalSubtrees(TreeNode root, int[] count) {
    if (root == null) {
        return false;
    }
    boolean left = isUnivalSubtrees(root.left, count);
    boolean right = isUnivalSubtrees(root.right, count);
    if (!left && !right) {
        if (root.left == null && root.right == null) {
            count[0]++;
            return true;
        }
    } else if (left && right) {
        if (root.left.val == root.val && root.right.val == root.val) {
            count[0]++;
            return true;
        }
    } else if (left && !right) {
        if (root.right == null && root.left.val == root.val) {
            count[0]++;
            return true;
        }
    } else if (!left && right) {
        if (root.left == null && root.right.val == root.val) {
            count[0]++;
            return true;
        }
    }
    return false;
}
FacebookTwitterGoogle+Share

Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

  • '?' Matches any single character.
  • '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

 Example
<code>isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false</code>

Solution1. Dynamic Programming

isMatch[i][j] = if first i chars for s can match first j chars of p

j==’*’: OR(isMatch[0~i][j-1])

j==’?’: isMatch[i-1][j-1]

else: isMatch[i-1][j-1] && s.charAt(i-1)==p.charAt(j-1)

public boolean isMatch(String s, String p) {
    //dp version
    if (s == null || p == null) {
        return false;
    }
    boolean[][] isMatch = new boolean[s.length() + 1][p.length() + 1];
    isMatch[0][0] = true;
    for (int i = 1; i <= s.length(); i++) {
        isMatch[i][0] = false;
    }
    for (int j = 1; j <= p.length(); j++) {
        isMatch[0][j] = isMatch[0][j - 1] && p.charAt(j - 1) == '*';
    }
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 1; j <= p.length(); j++) {
            if (p.charAt(j - 1) == '*') {
                for (int k = 0; k <= i; k++) {
                    if (isMatch[k][j - 1]) {
                        isMatch[i][j] = true;
                        break;
                    }
                }
            } else if (p.charAt(j - 1) == '?') {
                isMatch[i][j] = isMatch[i - 1][j - 1];
            } else {
                isMatch[i][j] = isMatch[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1);
            }
        }
    }
    return isMatch[s.length()][p.length()];
}

Leetcode: Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?1. O(m+n) space solutionAnalysis:
To achieve O(m+n) space, you need two array to store information while traversal the matrix for the first time checking if it is zero or not. You can also combine two arrays into one, but still cost O(m+n) space. So I just use two to store row and column information.
public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        boolean[] zeroRows = new boolean[matrix.length];
        boolean[] zeroCols = new boolean[matrix[0].length];
        //traversal the entire matrix to check if it is zero or not
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    zeroRows[i] = true;
                    zeroCols[j] = true;
                }
            }
        }
        //now set matrix zero based on the two boolean arrays
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (zeroRows[i] || zeroCols[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

2. *Optimal* O(1) space solution

Analysis:
To save space, we can just make use of the space inside the matrix. Which means, we use the first row and first column to store the information.
In the first traversal, we set the corresponding cell on the first row or first column to 0 if there is any cell which is zero in this row or column.
In the second traversal, we set the matrix to zeros based on the first row and first column.

 public void setZeroes(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;
        //traversal the entire matrix to check if it is zero or not
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    if (i == 0) {
                        firstRowHasZero = true;
                    }
                    if (j == 0) {
                        firstColHasZero = true;
                    }
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        //now set matrix zero based on first row and first column
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
//deal with the first column
        if (firstColHasZero) {
            for (int i = 1; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
//deal with the first row
        if (firstRowHasZero) {
            for (int i = 1; i < matrix[0].length; i++) {
                matrix[0][i] = 0;
            }
        }
    }

Note: The tricky part of this algorithm is, if without those two boolean variables to keep track of if there is any zero in the first row or first column , when matrix[0][0]==0, we have no idea if the first row contains zero, or it is the first column contains zero, or both. also, we should deal with the rest part first based on the first row and first column and then deal with the first row and first column based on the two boolean values.

Leetcode: Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

1. Recursive Solution

 public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int[][] resultMap = new int[grid.length][grid[0].length];
        return minPathSum(grid, resultMap, grid.length-1, grid[0].length-1);
    }

    public int minPathSum(int[][] grid, int[][] resultMap, int row, int col) {
        if (row < 0 || col < 0) {
            return Integer.MAX_VALUE;
        }
        if (row == 0 && col == 0) {
            return grid[0][0];
        }
        if (resultMap[row][col] == 0) {
            resultMap[row][col] = grid[row][col] + Math.min(minPathSum(grid, resultMap, row - 1, col), minPathSum(grid, resultMap, row, col - 1));
        }
        return resultMap[row][col];
    }

Note:

This is a very typical dp problem. where dp[i][j] = grid[i][j] + min( dp[i-1][j], dp[i][j-1] ); To prevent same cell being visited and calculated multiple times, we have a resultMap 2d array to store the result. We also need to check the edge carefully to ensure the index is not out of bounds of the given array.

2. Iterative Solution (O(m*n) space)

public class Solution {
     public int minPathSum(int[][] grid) {
        if(grid.length==0||grid[0].length==0){
            return 0;
        }
        //2D map -- O(m*n) space
        int[][] resultMap = new int[grid.length][grid[0].length];
        resultMap[0][0] = grid[0][0];
        //Calculate the first row
        for(int i = 1;i<grid[0].length;i++){
            resultMap[0][i] = grid[0][i] + resultMap[0][i-1];
        }
        //Calculate the first col
        for(int i = 1;i<grid.length;i++){
            resultMap[i][0] = grid[i][0] + resultMap[i-1][0];
        }
        //Calculate the rest
        for(int i=1;i<grid.length;i++){
            for(int j=1;j<grid[0].length;j++){
                resultMap[i][j] = grid[i][j]+Math.min(resultMap[i-1][j],resultMap[i][j-1]);
            }
        }
        return resultMap[grid.length-1][grid[0].length-1];
    }
}

Note: First calculate first row and first col which is there own grid value, then calculate other cells based on it.

3. *Optimal* Iterative Solution (O(n) space)

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;

        //1D map -- O(n) space, n is # of cols
        int[] resultMap = new int[cols];
        resultMap[0] = grid[0][0];

        //Calculate the first row
        for (int i = 1; i < grid[0].length; i++) {
            resultMap[i] = grid[0][i] + resultMap[i - 1];
        }

        for (int i = 1; i < rows; i++) {
            resultMap[0] = resultMap[0] + grid[i][0];
            for (int j = 1; j < cols; j++) {
                resultMap[j] = grid[i][j] + Math.min(resultMap[j], resultMap[j - 1]);
            }
        }
        return resultMap[cols - 1];
    }
}

Note: You don’t necessarily need a 2d map to store which cost O(n) space where n is the # of columns. You can just use one row to stored the result of previous row, and replace the value with the current row from left to right one by one. One thing worth mentioning is this code is more space efficient though, it has lower readability.

More information and further thoughts for minimum path sum questions can be found here.

Leetcode: Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution: One Pass O(n) time.

For each day i,

1. think of if sell it at day i, compare the profit with maxProfit.

2. check if day i is a better day than any previous day to buy a stock, meaning the price is cheaper than any previous day, then we buy the stock at day i.

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int maxProfit = 0;
    int sum = 0;
    int buyDate = 0;
    for (int i = 1; i < prices.length; i++) {
        maxProfit = Math.max(maxProfit, prices[i] - prices[buyDate]);
        if (prices[i] < prices[buyDate]) {
            buyDate = i;
        }
    }
    return maxProfit;
}

 

Leetcode: Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int start = 0;
        int end = m * n - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            int midVal = matrix[mid / n][mid % n];
            if (midVal == target) {
                return true;
            } else if (midVal > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return false;
    }
}

Note: O(log(m*n))

Leetcode: Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        if (root == null) {
            return result;
        }
        List<TreeNode> currLevel = new LinkedList<TreeNode>();
        currLevel.add(root);
        while (currLevel.size() > 0) {
            result.add(0, new LinkedList<Integer>());
            List<TreeNode> nextLevel = new LinkedList<TreeNode>();
            while (currLevel.size() > 0) {
                TreeNode runner = currLevel.remove(0);
                result.get(0).add(runner.val);
                if (runner.left != null) {
                    nextLevel.add(runner.left);
                }
                if (runner.right != null) {
                    nextLevel.add(runner.right);
                }
            }
            currLevel = nextLevel;
        }
        return result;
    }
}

Leetcode: Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

    public int maxArea(int[] height) {
        int maxArea = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            maxArea = Math.max(maxArea, calculateArea(height, left, right));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }

    public int calculateArea(int[] height, int left, int right) {
        return Math.abs(right - left) * Math.min(height[left], height[right]);
    }

Note:

For any container, its volume depends on the shortest board.

Two-pointer scan. And always move with shorter board index.

Leetcode: Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        if (n <= 1 || matrix.length <= 1 || n != matrix.length) {
            return;
        }
        int mid = (n - 1) / 2;
        int offset = 0;
        while (offset <= mid) {
            for (int i = offset; i < n - 1 - offset; i++) {
                int tmp = matrix[offset][i];
                matrix[offset][i] = matrix[n - 1 - i][offset];
                matrix[n - 1 - i][offset] = matrix[n - 1 - offset][n - 1 - i];
                matrix[n - 1 - offset][n - 1 - i] = matrix[i][n - 1 - offset];
                matrix[i][n - 1 - offset] = tmp;
            }
            offset++;
        }

    }
}