73. Set Matrix Zeroes

📝 Problem Details

• Title: 73. Set Matrix Zeroes
• Link: https://leetcode.com/problems/set-matrix-zeroes/
• Difficulty: Medium
• Tags/Categories: Math Matrix

input n x m integer matrix matrix if an element is 0, set its entire row and column to zeros must be done in place

💡 Explanation of Solution

Use the first row and first column of the matrix itself to store markers for which rows and columns should be zeroed out

1. first pass: identify which rows and columns should be set to zero
	- use the first row to track which columns should be set to zero
	- use the first column to track which rows should be set to zero
	- maintain two boolean flags firstRowZero, firstColZero to track if the first row/column itself needs to be zeroed

2. second pass: iterate through the matrix (excluding the first row/column) and set elements to zero based on markers

3. final pass: zero out the first row and / or first column if needed  

⌛ Complexity Analysis

Time Complexity: O(n*m)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool firstRowZero = false;
        bool firstColZero = false;
 
        // step 1: identify which rows and cols need to be zeroed
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 0) {
                    if(i == 0) firstRowZero = true;
                    if(j == 0) firstColZero = true;
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
 
        // step 2: zero out cells based on markers
        // (excluding first row and column)
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
 
        // step 3 : zero out first row if needed 
        if (firstRowZero) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }        
 
        // step 4 : zero out first column if needed 
        if (firstColZero) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
};