73. Set Matrix Zeroes

Description

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

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

Examples

Example 1

Input: [ [1, 1, 1], [1, 0, 1], [1, 1, 1] ]

Output: [ [1, 0, 1], [0, 0, 0], [1, 0, 1] ]

Example 2

Input: [ [0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5] ]

Output: [ [0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0] ]

Solutions

Solution 1

/**
 * Time complexity : O((M×N)×(M+N)) where M and N are the number of rows and columns 
 *    respectively. Even though this solution avoids using space, but is very 
 *    inefficient since in worst case for every cell we might have to zero out its 
 *    corresponding row and column. Thus for all (M×N) cells zeroing out (M+N) cells.
 * Space complexity : O(1)
 */

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int MAX = -1000000;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(matrix[i][j] == 0) {
                    for(int k = 0; k < row; k++) {
                        if(matrix[k][j] != 0) {
                            matrix[k][j] = MAX;
                        }
                    }
                    for(int k = 0; k < col; k++) {
                        if(matrix[i][k] != 0) {
                            matrix[i][k] = MAX;
                        }
                    }
                }
            }
        }
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(matrix[i][j] == MAX) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

Solution 2

/**
 * Time complexity : O(M×N)
 * Space complexity : O(1)
 */

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int col0 = 1;
        for(int i = 0; i < row; i++) {
            if(matrix[i][0] == 0) col0 = 0;
            for(int j = 1; j < col; j++) {
                if(matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i = row-1; i >= 0; i--) {
            for(int j = col-1; j >= 1; j--) {
                if(matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if(col0 == 0) matrix[i][0] = 0;
        }
    }
}

Follow up

• 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?