Leetcode–Set Matrix Zeroes

The Problem:

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

 

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?

Notes:

  1. A simple O(m+n) solution is to record the row/column needs to reset. If we are strict on the space, one way to do it is to reuse the matrix itself. For example we can use the first row to record the columns needs to reset, and only need one other flag to tell if the first row itself needs reset.

Java Solution

public class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        if(n==0 || m==0) return;
        boolean row0 = false;
        for(int j = 0; j < m; j++){
            if(matrix[0][j]==0){
                row0 = true;
            }
        }
        for(int i = 1; i < n; i++ ){
            boolean hasZero = false;
            for(int j = 0; j < m; j++){
                if(matrix[i][j]==0){
                    matrix[0][j]= 0;
                    hasZero = true;
                }
            }
            if(hasZero){
                for(int j = 0; j < m; j++){
                    matrix[i][j] = 0;
                }
            }
        }
        for(int j = 0; j < m ; j++){
            if(matrix[0][j] == 0){
                for(int i = 1; i < n; i++){
                    matrix[i][j] = 0;
                }
            }
        }
        if(row0){
            for(int j = 0; j < m; j++)
                matrix[0][j] = 0;
        }
        return;
    }
}
Advertisements

Leetcode–Decode Ways

The Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Notes:

  1. A DP problem. An important observation is that for multi-way sequences  such as  ‘1”2’, the regression function is ways[i] = ways[i-1] + ways[i-2]
  2. Watch out for details:
    1. ‘0’ can only pair with previous ‘1’ or ‘2’, which means ways[i] = ways[i-2]
    2. when using ways[i-2] need to check the bounds

Java Solution

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(n==0)return 0;
        int[] ways = new int[n];
        if(s.charAt(0)=='0')
            return 0;
        else
            ways[0] = 1;
            
        for(int i = 1; i < n; i++){
            if(s.charAt(i)=='0'){ // only valid if previous is 1 or 2
                if(s.charAt(i-1)=='2'||s.charAt(i-1)=='1'){
                    ways[i] = i>=2 ? ways[i-2]:1;
                }
                else
                    return 0;
            }
            else{
                if(isValid(s.charAt(i-1), s.charAt(i))){
                    // have multiple ways
                    ways[i] = i>=2 ? ways[i-1]+ways[i-2] : 2;
                }
                else{
                    ways[i] =ways[i-1];
                }
            }
        }
        return ways[n-1];
    }
    
    private boolean isValid(char a, char b){
        if(a=='1')
            return true;
        if(a=='2' && b <= '6')
            return true;
        return false;
    }
}

Leetcode–Maximal Rectangle

The Problem:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

Notes:

  1. A DP problem, think of handle each row/column first, get the max length for that row/column, and store it in a 2d array.
  2. Another thing worth mentioning is in the second round, for each non-zero grid should consider a new sequence start from this index since the minrow will change.

Java Solution

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0 || matrix[0].length==0)return 0;
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] area = new int[n][m];
        for(int j = 0; j <m; j++){
            area[0][j] = matrix[0][j]=='0'?0:1;
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j]=='0'){
                    area[i][j]=0;
                }
                else{
                    area[i][j] = area[i-1][j]+1;
                }
            }
        }
        int maxarea = 0;
        int minrow;
        for(int i = 0; i < n; i++){
            for(int j=0; j<m;j++){
                if(area[i][j]!=0){
                    minrow= area[i][j];
                    maxarea = Math.max(maxarea,area[i][j]);
                    // from each nonzero grid, start a new try, because min can change
                    for(int k = j+1; k < m; k++){
                        if(area[i][k]==0)
                            break;
                        minrow = Math.min(area[i][k], minrow);
                        maxarea = Math.max(maxarea, minrow * (k-j+1));
                    }
                }
            }
        }
        return maxarea;
    }
}

Leetcode–Minimum Path Sum

The Problem:

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.

Notes:

  1. A basic DP problem, use the exact same approach as in Unique Path.

Java Solution

public class Solution {
    public int minPathSum(int[][] grid) {
        if(grid.length==0 || grid[0].length==0)return 0;
        int m = grid.length;
        int n = grid[0].length;
        int[][] path = new int[m][n];
        path[0][0] = grid[0][0];
        for(int i = 1; i < m; i++){
            path[i][0] = path[i-1][0]+grid[i][0];
        }
        for(int j = 1; j < n; j++){
            path[0][j] = path[0][j-1] + grid[0][j];
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                path[i][j] = Math.min(path[i-1][j], path[i][j-1]) + grid[i][j];
            }
        }
        return path[m-1][n-1];
        
    }
}

Leetcode–Unique Paths II

The Problem:

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3×3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

Notes:

  1. A basic DP problem, use the exact same approach as in Unique Path, only to mark those 1s to 0 in the path array. Remember that for the first row/column if there is a 1 , then all the subsequent entries should be 0.

Java Solution

  public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] path= new int[m][n];
        boolean blocked = false;
        for(int j = 0; j < n; j++){
            if(obstacleGrid[0][j]==1){
                blocked = true;
            }
            path[0][j] =  blocked? 0: 1;
        }
        blocked = false;
        for(int i = 0; i < m; i++){
            if(obstacleGrid[i][0]==1){
                blocked = true;
            }
            path[i][0] = blocked? 0: 1;
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                 if(obstacleGrid[i][j]==1){
                     path[i][j]=0;
                 }
                 else{
                    path[i][j] = path[i-1][j]+path[i][j-1];
                 }
            }
        }
        return path[m-1][n-1];
    }
}

Leetcode–Unique Paths

The Problem:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Notes:

  1. A basic DP problem, and also can be done by directly calculate choose m from (m+n).

Java Solution

  public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] path= new int[m][n];
        for(int j = 0; j < n; j++){
            path[0][j] = 1;
        }
        for(int i = 0; i < m; i++){
            path[i][0] = 1;
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                path[i][j] = path[i-1][j]+path[i][j-1];
            }
        }
        return path[m-1][n-1];
    }
} 

Leetcode–Maximum Subarray

The Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Notes:

  1. A basic DP problem

Java Solution

public class Solution {
    public int maxSubArray(int[] A) {
        if(A.length==0)return 0;
        int[] maxEndwith = new int[A.length];
        maxEndwith[0] = A[0];
        int max = maxEndwith[0];
        for(int i = 1; i < A.length; i++){
            if(maxEndwith[i-1] >0){
                maxEndwith[i] = maxEndwith[i-1] + A[i];
            }
            else{
                maxEndwith[i] = A[i];
            }
            max = Math.max(max, maxEndwith[i]);
        }
        return max;
    }
}