Today I have done leetcode's May LeetCoding Challenge with cpp.

May LeetCoding Challenge 21

Description

Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

Follow up:

• A straightforward solution using O(mn) 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?

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  void setZeroes(vector<vector<int>>& matrix) {
    bool firstRow = false;
    bool firstCol = false;
    int rows = matrix.size();
    int cols = matrix.front().size();
    for(int i = 0; i < rows; ++i) {
      if(!matrix[i][0]) firstCol = true;
    }
    for(int i = 0; i < cols; ++i) {
      if(!matrix[0][i]) firstRow = true;
    }
    for(int i = 1; i < rows; ++i) {
      for(int j = 0; j < cols; ++j) {
        if(!matrix[i][j]) {
          matrix[0][j] = 0;
          matrix[i][0] = 0;
        }
      }
    }
    for(int i = 1; i < rows; ++i) {
      if(!matrix[i][0]) {
        for(int j = 1; j < cols; ++j) {
          matrix[i][j] = 0;
        }
      }
    }
    for(int i = 1; i < cols; ++i) {
      if(!matrix[0][i]) {
        for(int j = 1; j < rows; ++j) {
          matrix[j][i] = 0;
        }
      }
    }
    if(firstCol) {
      for(int j = 0; j < rows; ++j) {
        matrix[j][0] = 0;
      }
    }
    if(firstRow) {
      for(int j = 0; j < cols; ++j) {
        matrix[0][j] = 0;
      }
    }
  }
};

// Accepted
// 202/202 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 52.14 % of cpp submissions (18.6 MB)