Straightforward In-place C++ Solution Using Set to Record Rows and Cols with Zeros


  • 0
    X

    My way traverse the matrix twice:

    • First pass: record col and row number of the 0 elements
    • Second pass: set corresponding rows and cols to all 0s.

    O(1) space with O(mn) time complexity.

    class Solution {
    public:
        void setZeroes(vector<vector<int>>& matrix) {
            int m = matrix.size(); if (!m) return;
            int n = matrix[0].size(); if (!n) return;
            
            unordered_set<int> col;
            unordered_set<int> row;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == 0) {
                        col.insert(j);
                        row.insert(i);
                    }
                }
            }
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (row.find(i) != row.end() || col.find(j) != col.end()) {
                        matrix[i][j] = 0;
                    }
                }
            }
            
        }
    };
    

  • 0
    N

    You are using a set. It is not constant space. What if all the elements are 0s.


Log in to reply
 

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