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.

FacebookTwitterGoogle+Share

Leetcode: Best Time to Buy and Sell Stock II

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

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

public class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int buyDay = -1; //keep track of the index of last buyDay
        int runner = 0;
        while (runner < prices.length-1) {
            if (runner + 1 < prices.length) {
                if (buyDay == -1 && prices[runner + 1] > prices[runner]) {
                    buyDay = runner;
                }
                if (buyDay != -1 && prices[runner + 1] < prices[runner]) {
                    maxProfit += prices[runner] - prices[buyDay];
                    buyDay = -1;
                }
            }
            runner++;
        }
        if (buyDay != -1 && prices[runner] > prices[buyDay]) {
            maxProfit += prices[runner] - prices[buyDay];
        }
        return maxProfit;
    }
}

Note:
Use a runner starting from the beginning of the array. Also need a variable called buyDay to keep track of the last buy day. -1 means there is no buy order yet or a sell order has just been placed, aka, next step is to buy. if buyDay equals to other integers, means next step is to sell.

When to Buy:
If next step is to buy and the price is increasing(means the price of next day is higher than the price of current day).

When to Sell:
If next step is to sell and the price is decreasing. the profit should be calculated and added to the maxProfit when sell order is placed.
Remember to check the edge cases, when it is the last day, there is no way to check if the price is increasing or decreasing. So just check if it has higher price than the buyDay.

Time Complexity:
O(n) only need to go through the array once.

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.