73. Set Matrix Zeroes

https://leetcode.com/problems/set-matrix-zeroes/

Problem

Given an 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(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?

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

Solution

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty()) return;
        bool zero_first_row = false, zero_first_col = false;
        if (matrix[0][0] == 0) {
            zero_first_row = zero_first_col = true;
        } else {
            for (int i = 1; i < matrix.size(); ++i) {
                if (matrix[i][0] == 0) {
                    zero_first_col = true; break;
                }
            }
            for (int i = 1; i < matrix[0].size(); ++i) {
                if (matrix[0][i] == 0) {
                    zero_first_row = true; break;
                }
            }
        }
        for (int i = 1; i < matrix.size(); ++i) {
            for (int j = 1; j < matrix[0].size(); ++j) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        for (int i = 1; i < matrix.size(); ++i) {
            if (matrix[i][0] == 0) fillHorizontal(matrix, i);
        }
        
        for (int i = 1; i < matrix[0].size(); ++i) {
            if (matrix[0][i] == 0) fillVertical(matrix, i);
        }
        
        if (zero_first_row) fillHorizontal(matrix, 0);
        if (zero_first_col) fillVertical(matrix, 0);
        
    }
    inline void fillHorizontal(vector<vector<int>>& matrix, int row) {
        for (int i = 0; i < matrix[0].size(); ++i) matrix[row][i] = 0;
    }
    inline void fillVertical(vector<vector<int>>& matrix, int col) {
        for (int i = 0; i < matrix.size(); ++i) matrix[i][col] = 0;
    }
};

• #encoding