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?

Approach

• If we see any zero then mark the that column and row’s first element as zero this is later used to mark all rows and columns as zeros
• We also need to check for first row and col as all the operation above would be done starting from 1
• Time: O(m*n) Space: O(1)
• First we will check if any of 0th row or column is zero because if it is

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length, col = matrix[0].length;
        boolean fr = false, fc = false;    
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0)
                fr = true;
        }
 
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0)
                fc = true;
        }
		// mark row and col starting from 1
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
		//finally make them zero starting from 1
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
        }
		// handle first col and row separately
        if (fr) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
 
        if (fc) {
            for (int i = 0; i < col; i++) {
                matrix[0][i] = 0;
            }
        }
    }
}

💡 The Core Problem and the Strategy

If you change rows and columns to zero immediately while looping through the matrix, you will accidentally overwrite non-zero elements before checking them. You would end up turning the entire matrix into zeros!

To fix this without using extra memory:

1. Use variables fr and fc to remember if the very first row/column natively have zeros.
2. Use the rest of the first row and column as marker flags to store the zero locations for the inner matrix.
3. Process the inner matrix first.
4. Process the first row and column last.

---

🚶‍♂️ Step-by-Step Code Walkthrough

Step 1: Check the First Row and Column

java

boolean fr = false, fc = false;    
for (int i = 0; i < row; i++) {
    if (matrix[i][0] == 0) fr = true;
}
for (int j = 0; j < col; j++) {
    if (matrix[0][j] == 0) fc = true;
}

Use code with caution.

• What it does: It checks if there is any 0 sitting natively in the 0th column or the 0th row.
• Why: We are about to overwrite these cells with our tracking scoreboard, so we need to save their original status in fr (First Row) and fc (First Column) flags first.

Step 2: Use First Row/Col as a “Scoreboard”

java

for (int i = 1; i < row; i++) {
    for (int j = 1; j < col; j++) {
        if (matrix[i][j] == 0) {
            matrix[i][0] = 0; // Mark the row header
            matrix[0][j] = 0; // Mark the column header
        }
    }
}

Use code with caution.

• What it does: Loops through the inner matrix (starting index 1). If it finds a 0 at position (i, j), it goes to the edge of the matrix and sets matrix[i][0] = 0 and matrix[0][j] = 0.
• Analogy: Think of the first row and column as light switches. Finding a zero inside flicks the corresponding row and column switches to “off” (0).

Step 3: Update the Inner Matrix Based on Scoreboard

java

for (int i = 1; i < row; i++) {
    for (int j = 1; j < col; j++) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0)
            matrix[i][j] = 0;
    }
}

Use code with caution.

• What it does: Loops through the inner matrix again. It looks at the header of the current row matrix[i][0] and column matrix[0][j]. If either header is 0, it safely turns the current cell matrix[i][j] into 0.

Step 4: Handle the First Row and Column Last

java

if (fr) {
    for (int i = 0; i < row; i++) matrix[i][0] = 0;
}
if (fc) {
    for (int i = 0; i < col; i++) matrix[0][i] = 0;
}

Use code with caution.

• What it does: Finally, it checks the boolean flags we saved in Step 1. If fr was true, it turns the entire first row to zeros. If fc was true, it turns the entire first column to zeros.

---

📊 Complexity Analysis

• Time Complexity: O(M × N) where M is rows and N is columns. We traverse the matrix a few times, but it is purely linear work.
• Space Complexity: O(1) Auxiliary Space. No extra arrays or hash sets were created. The memory remains constant because we manipulated the input matrix directly.

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        
        // Trackers to see if the first row or first column contain any native zeros
        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;    
        
        // 1. Scan the FIRST COLUMN (Column 0) downwards across all rows
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                firstColHasZero = true;
            }
        }
 
        // 2. Scan the FIRST ROW (Row 0) sideways across all columns
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                firstRowHasZero = true;
            }
        }
        
        // 3. Scan the INNER MATRIX (starting at index 1)
        // Use the first row and column headers as a scoreboard
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0; // Mark the row header
                    matrix[0][j] = 0; // Mark the column header
                }
            }
        }
        
        // 4. Update the INNER MATRIX based on the scoreboard headers
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // 5. Handle the FIRST COLUMN separately using the tracker variable
        if (firstColHasZero) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
 
        // 6. Handle the FIRST ROW separately using the tracker variable
        if (firstRowHasZero) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}
 

• Easier one that doesn’t require swap names, this is easy col with col and row with row

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