ac solution code


  • 0
        /*
         Solution1. time = O(mn); space = O(1) 
         https://discuss.leetcode.com/topic/5056/any-shorter-o-1-space-solution
         Use first row and first column to if row/column has any 0, then set the whole row/column to 0, trick is set cache first column to avoid being overriden.  (in place)
         
         My idea is simple: store states of each row in the first of that row, and store states of each column in the first of that column. 
         Because the state of row0 and the state of column0 would occupy the same cell, I let it be the state of row0, and use another 
         variable "col0" for column0. In the first phase, use matrix elements to set states in a top-down way. In the second phase, 
         use states to set matrix elements in a bottom-up way.
         */
        func setZeroes(_ matrix: inout [[Int]]) {
            guard matrix.count > 0 else {return}
            var col0 = 1, rows = matrix.count, cols = matrix[0].count
            for i in 0..<rows {
                if matrix[i][0] == 0 {// Use col0 to save result(0) of col 0 (temp varaible)
                    col0 = 0
                }
                for j in 1..<cols {
                    if matrix[i][j] == 0 {// Use first row and first column to save the result. (in place)
                        matrix[i][0] = 0
                        matrix[0][j] = 0
                    }
                }
            }
            
            for i in stride(from: rows - 1, through: 0, by: -1) {
                for j in stride(from: cols - 1, through: 1, by: -1) {
                    if matrix[i][0] == 0 || matrix[0][j] == 0 {// if first row or first col is 0, then set whole row/col to 0
                        matrix[i][j] = 0
                    }
                }
                if col0 == 0 {// If col0 is 0, then set first col to 0
                    matrix[i][0] = 0
                }
            }
        }
    

Log in to reply
 

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