84ms in-place C++ solution


  • 0
    S

    The Idea is to find the first zero at matrix[m][n], and use row m and column n to mark zero rows and columns.

    class Solution {
    public:
        void setZeroes(vector<vector<int>>& matrix) {
            int m = 0;
            int n = 0;
            bool foundZero = false;
            
            for (m = 0; m<matrix.size(); m++) {
                for (n = 0; n<matrix[m].size(); n++) {
                    if (matrix[m][n] == 0) {
                        foundZero = true;
                        break;
                    }
                }
                if (foundZero) break;
            }
            if (!foundZero) return;
            
            //use row m, column n, to mark zero rows and columns
            for (int i = m; i < matrix.size(); i++) {
                for (int j = 0; j < matrix[i].size(); j++) {
                    if (matrix[i][j] == 0) {
                        matrix[m][j] = 0;
                        matrix[i][n] = 0;
                    }
                }
            }
            
            //set zero
            for (int i = 0; i < matrix.size(); i++) {
                if (i == m || matrix[i][n] != 0) continue;
                //set matrix[i][:] zero
                fill(matrix[i].begin(), matrix[i].end(), 0);
            }
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[m][j] != 0) continue;
                //set matrix[:][j] to zero
                for (int i = 0; i < matrix.size(); i++) {
                    matrix[i][j] = 0;
                }
            }
            
            //set row m to zero
            fill(matrix[m].begin(), matrix[m].end(), 0);
        }
    };

Log in to reply
 

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