Question

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:

• A straight forward solution using O(m__n) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

Difficulty:Medium

Category:Array

Analyze

Solution

class Solution {
 public:
  void setZeroes(vector<vector<int>>& matrix) {
    const unsigned int len_r = matrix.size();
    const unsigned int len_c = matrix[0].size();

    bool done_r[len_r] = {false};
    bool done_c[len_c] = {false};

    // Check each row
    for (int i = 0; i < len_r; ++i) {
      for (int j = 0; j < len_c; ++j) {
        if (matrix[i][j] == 0) {
          done_c[j] = true;
          done_r[i] = true;
        }
      }
    }

    for (int i = 0; i < len_r; ++i) {
      if (done_r[i]) {
        for (int j = 0; j < len_c; ++j) {
          matrix[i][j] = 0;
        }
      }
    }

    for (int i = 0; i < len_c; ++i) {
      if (done_c[i]) {
        for (int j = 0; j < len_r; ++j) {
          matrix[j][i] = 0;
        }
      }
    }
    // Check each column
  }
};