In-place solution using constant space in C++, best submission


  • 6
    • store the status of the line and column in the top-most or left-most
    • before that we should check the top-most row and left-most column and store their status first
    class Solution {
    public:
        void setZeroes(vector<vector<int>>& matrix) 
        {
            if(matrix.empty()) return ;
            int rowSize = matrix.size(), colSize = matrix[0].size();
            bool firstRow = false, firstCol = false;
            for(int c = 0; c < colSize; ++c) if(matrix[0][c] == 0) firstRow = true;
            for(int r = 0; r < rowSize; ++r) if(matrix[r][0] == 0) firstCol = true;
            for(int r = 1; r < rowSize; ++r)
                for(int c = 1; c < colSize; ++c)
                    if(matrix[r][c] == 0) matrix[0][c] = matrix[r][0] = 0;
            for(int c = 1; c < colSize; ++c) 
                if(matrix[0][c] == 0)
                    for(int r = 1; r < rowSize; ++r)
                        matrix[r][c] = 0;
            for(int r = 1; r < rowSize; ++r) 
                if(matrix[r][0] == 0)
                    for(int c = 1; c < colSize; ++c)
                        matrix[r][c] = 0;
            if(firstRow) for(int c = 0; c < colSize; ++c) matrix[0][c] = 0;
            if(firstCol) for(int r = 0; r < rowSize; ++r) matrix[r][0] = 0;
        }
    };
    

  • 2
    S

    @LHearen why always you ?!


  • 0

    @sy1121 What do you mean exactly?


  • 0
    F

    @LHearen I guess he means why you can always get the best submission, and that's exactly what I want to say, haha...
    Again, thanks for your brilliant idea!


  • 0

    I guess my Java solution utilizes the same idea.

    public class Solution {
        public void setZeroes(int[][] matrix) {
            if (matrix.length == 0 || matrix[0].length == 0) return;
            
            boolean firstRowZero = false;
            boolean firstColZero = false;
            
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == 0) {
                        if (i == 0 && j == 0) {
                            firstRowZero = true;
                            firstColZero = true;
                        } else if (i == 0) {
                            firstRowZero = true;
                        } else if (j == 0) {
                            firstColZero = true;
                        } else {
                            matrix[i][0] = 0;
                            matrix[0][j] = 0;
                        }
                    }
                }
            }
            
            for (int i = 1; i < matrix.length; i++)
                for (int j = 1; j < matrix[0].length; j++)
                    if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            
            if (firstRowZero) for (int j = 0; j < matrix[0].length; j++) matrix[0][j] = 0;
            if (firstColZero) for (int i = 0; i < matrix.length; i++) matrix[i][0] = 0;
        }
    }
    

Log in to reply
 

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