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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s