Given an m x n matrix, if an element is zero, set its entire row and column to zero. The challenge is to perform this modification in place without using extra matrix storage. The key idea: use the first row and first column as flag storage to record which rows and columns need zeroing, then apply the changes in a final pass.

Algorithm Outline

1. Check original state of first row/column: Since we will overwrite these cells as markers, first record whether the first row or first column originally contained any zero.
2. Mark zero rows/columns using first row/column: Traverse the rest of the matrix (excluding first row and column). For each matrix[i][j] that is zero, set matrix[i][0] = 0 (mark row i) and matrix[0][j] = 0 (mark column j).
3. Zero out non‑first rows and columns: Using the markers from step 2, set entire rows and columns to zero (except the first row and column).
4. Zero the first row and column: Apply the original flags saved in step 1 to clean the first row and column if needed.

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        bool rowZeroFlag = false;  // true if first row initially has a zero
        bool colZeroFlag = false;  // true if first column initially has a zero

        // 1. Check first row
        for (int c = 0; c < cols; ++c) {
            if (matrix[0][c] == 0) {
                rowZeroFlag = true;
                break;
            }
        }

        // 2. Check first column
        for (int r = 0; r < rows; ++r) {
            if (matrix[r][0] == 0) {
                colZeroFlag = true;
                break;
            }
        }

        // 3. Use first row/col as markers for the rest
        for (int r = 1; r < rows; ++r) {
            for (int c = 1; c < cols; ++c) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0;  // mark row r
                    matrix[0][c] = 0;  // mark column c
                }
            }
        }

        // 4. Zero out rows and columns (excluding first row/col) based on markers
        for (int r = 1; r < rows; ++r) {
            if (matrix[r][0] == 0) {
                for (int c = 1; c < cols; ++c) {
                    matrix[r][c] = 0;
                }
            }
        }
        for (int c = 1; c < cols; ++c) {
            if (matrix[0][c] == 0) {
                for (int r = 1; r < rows; ++r) {
                    matrix[r][c] = 0;
                }
            }
        }

        // 5. Handle first row and column
        if (rowZeroFlag) {
            for (int c = 0; c < cols; ++c) {
                matrix[0][c] = 0;
            }
        }
        if (colZeroFlag) {
            for (int r = 0; r < rows; ++r) {
                matrix[r][0] = 0;
            }
        }
    }
};

// Test
int main() {
    vector<vector<int>> mat = {{1,1,1}, {1,0,1}, {1,1,1}};
    Solution sol;
    sol.setZeroes(mat);
    for (auto& row : mat) {
        for (int v : row) cout << v << " ";
        cout << endl;
    }
    return 0;
}

Complexity & Critical Points

• Time Complexity: O(rows × cols) — each element is visited a constant number of times.
• Space Complexity: O(1) — only two boolean flags are used, satisfying the in‑place requirement.
• Why separate flags for first row/column? The markers themselves live in the first row and column. Without preserving their original state, we would lose the information and might incorrectly zero the entire first row/column when only a marker (not a original zero) exists there.
• Processing order matters: Non‑first rows/columns must be zeroed before handling the first row and column. If we zeroed the first row/column first, we would overwrite the markers needed for step 4.