Code Implementation

class Solution:
    def setZeroes(self, matrix):
        if not matrix or not matrix[0]:
            return
        rows, cols = len(matrix), len(matrix[0])
        first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
        first_col_zero = any(matrix[i][0] == 0 for i in range(rows))
        
        # Use first row and column as markers
        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        
        # Set zeroes based on markers
        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        
        # Zero first row and column if needed
        if first_row_zero:
            for j in range(cols):
                matrix[0][j] = 0
        if first_col_zero:
            for i in range(rows):
                matrix[i][0] = 0
      

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int rows = matrix.size(), cols = matrix[0].size();
        bool firstRowZero = false, firstColZero = false;
        for (int i = 0; i < rows; ++i)
            if (matrix[i][0] == 0) firstColZero = true;
        for (int j = 0; j < cols; ++j)
            if (matrix[0][j] == 0) firstRowZero = true;
        for (int i = 1; i < rows; ++i)
            for (int j = 1; j < cols; ++j)
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
        for (int i = 1; i < rows; ++i)
            for (int j = 1; j < cols; ++j)
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
        if (firstRowZero)
            for (int j = 0; j < cols; ++j) matrix[0][j] = 0;
        if (firstColZero)
            for (int i = 0; i < rows; ++i) matrix[i][0] = 0;
    }
};
      

class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        boolean firstRowZero = false, firstColZero = false;
        for (int i = 0; i < rows; i++)
            if (matrix[i][0] == 0) firstColZero = true;
        for (int j = 0; j < cols; j++)
            if (matrix[0][j] == 0) firstRowZero = true;
        for (int i = 1; i < rows; i++)
            for (int j = 1; j < cols; j++)
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
        for (int i = 1; i < rows; i++)
            for (int j = 1; j < cols; j++)
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
        if (firstRowZero)
            for (int j = 0; j < cols; j++) matrix[0][j] = 0;
        if (firstColZero)
            for (int i = 0; i < rows; i++) matrix[i][0] = 0;
    }
}
      

var setZeroes = function(matrix) {
    let rows = matrix.length, cols = matrix[0].length;
    let firstRowZero = false, firstColZero = false;
    for (let i = 0; i < rows; i++)
        if (matrix[i][0] === 0) firstColZero = true;
    for (let j = 0; j < cols; j++)
        if (matrix[0][j] === 0) firstRowZero = true;
    for (let i = 1; i < rows; i++)
        for (let j = 1; j < cols; j++)
            if (matrix[i][j] === 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
    for (let i = 1; i < rows; i++)
        for (let j = 1; j < cols; j++)
            if (matrix[i][0] === 0 || matrix[0][j] === 0)
                matrix[i][j] = 0;
    if (firstRowZero)
        for (let j = 0; j < cols; j++) matrix[0][j] = 0;
    if (firstColZero)
        for (let i = 0; i < rows; i++) matrix[i][0] = 0;
};
      

Problem Description

You are given a 2D matrix of integers called matrix. If an element in matrix is 0, you must set its entire row and column to 0. This operation must be performed in-place (modify the original matrix, not create a new one).

• There is only one valid solution for the output.
• The same zero element cannot be used to set its row and column to zero more than once.
• Try to do it with as little extra space as possible.

For example, given matrix = [[1,1,1],[1,0,1],[1,1,1]], after running the function, matrix should become [[1,0,1],[0,0,0],[1,0,1]].

Thought Process

The straightforward way to solve this problem is to scan the matrix and, whenever a 0 is found, mark all elements in its row and column to be zeroed. However, if we do this directly, we might overwrite non-zero values with 0s too early, causing us to lose information about the original matrix.

A brute-force approach could involve creating copies of the matrix or using extra arrays to remember which rows and columns should be zeroed. But the challenge is to do this in-place, using as little extra space as possible.

The key insight is to use the matrix itself to store "flags" that indicate which rows and columns need to be zeroed, instead of using extra arrays. This leads us to a space-optimized solution that cleverly reuses the first row and first column of the matrix as markers.

Solution Approach

Here is a step-by-step breakdown of the optimized approach:

1. Identify Zeroes in the First Row and First Column:
   • We need to know whether the first row or first column contain any zeroes, because we will use these as markers and might overwrite them.
2. Use First Row and First Column as Markers:
   • For every cell matrix[i][j] (except those in the first row or column), if it is zero, set matrix[i][0] and matrix[0][j] to zero. These act as flags to indicate that row i and column j should be zeroed.
3. Zero Out Marked Rows and Columns:
   • Iterate through the matrix (excluding first row and column). If matrix[i][0] or matrix[0][j] is zero, set matrix[i][j] to zero.
4. Zero Out the First Row and First Column if Needed:
   • If the first row originally had a zero, set all its elements to zero.
   • If the first column originally had a zero, set all its elements to zero.

This approach ensures that we only use constant extra space (just a couple of boolean flags), and the rest of the state is stored within the matrix itself.

Example Walkthrough

Let's walk through the solution with the example matrix = [[1,1,1],[1,0,1],[1,1,1]].

1. Initial Matrix:
   1 1 1
   1 0 1
   1 1 1
2. Scan for Zeroes in First Row/Column:
   None in first row or first column, so firstRowZero = False, firstColZero = False.
3. Mark Rows and Columns:
   At position (1,1), value is 0. Set matrix[1][0] = 0 and matrix[0][1] = 0.
   Matrix now looks like:
   1 0 1
   0 0 1
   1 1 1
4. Zero Out Marked Cells:
   For cells not in the first row/column, if their row or column is marked, set to 0:
   • (1,1) is already 0
   • (1,2): row marked (matrix[1][0]=0) → set to 0
   • (2,1): column marked (matrix[0][1]=0) → set to 0
   Updated matrix:
   1 0 1
   0 0 0
   1 0 1
5. Zero First Row/Column if Needed:
   Both firstRowZero and firstColZero are false, so nothing changes.
6. Final Matrix:
   1 0 1
   0 0 0
   1 0 1

This matches the expected output.

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O(M×N×(M+N)), since for every zero you might traverse its entire row and column.
  • Space Complexity: O(M+N) if you use extra arrays to store rows/columns to zero.
• Optimized Approach (First Row/Column Markers):
  • Time Complexity: O(M×N), because we traverse the matrix a constant number of times.
  • Space Complexity: O(1), because we only use a couple of boolean variables regardless of input size.

Summary

The Set Matrix Zeroes problem is a classic example of in-place array manipulation. The elegant solution leverages the matrix's first row and column as markers to avoid extra space, while careful bookkeeping ensures the original state is preserved until the end. This approach balances efficiency and clarity, and is a great illustration of optimizing both time and space complexity by reusing existing data structures.