Java beats 97.44% of solutions. With description.


  • -5
    S

    The basic idea here is to reduce space complexity by to keep the indexes of cells with value 0 separately in rows and columns arrays. Now, obviously these indexes will overlap, so in the worst case we can have all the rows or columns as 0. so the maximum size of rows and columns arrays can be m and n respectively. Hence, achieving space complexity of O(m + n)

    Now the code ...

    public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return;
        }
        
        int[] rows = new int[matrix.length];
        int[] columns = new int[matrix[0].length];
        
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0 ; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    rows[i] = 1;
                    columns[j] = 1;
                }
            }
        }
        
        for (int i = 0 ; i < rows.length; i++) {
            if (rows[i] == 1) {
                for (int j = 0 ; j < columns.length; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        for (int i = 0 ; i < columns.length; i++) {
            if (columns[i] == 1) {
                for (int j = 0 ; j < rows.length; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.