LeetCode 73: Set Matrix Zeroes – In-Place Solution (C++, Java, Python, C#)

Keywords: In-place matrix algorithm, O(1) space complexity, matrix row and column update, LeetCode walkthrough, zeroing matrix, C++, Java, Python, C# solutions

Problem Summary

Given an m x n matrix, if any element is 0, set its entire row and column to 0. This must be done in-place, using constant space.

Example

Input:

[[1,1,1],
 [1,0,1],
 [1,1,1]]

Output:

[[1,0,1],
 [0,0,0],
 [1,0,1]]

Optimized Approach (O(1) Space)

Instead of using extra arrays, we use the first row and first column of the matrix to mark rows and columns that should be zeroed. A separate flag (col0) is used to track if the first column needs to be zeroed (since matrix[0][0] is shared by both first row and column).

Steps:

Mark rows & columns:
- Iterate through the matrix.
- If matrix[i][j] == 0, mark matrix[i][0] = 0 and matrix[0][j] = 0.
- Track first column separately using col0.
Update inner matrix:
- Iterate in reverse to avoid premature overwriting.
- Set matrix[i][j] = 0 if the corresponding row or column is marked.
Handle first row & column:
- Use the markers and col0 flag to zero the first row/column if needed.

Code Implementations

C++

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int col0 = 1;
        for (int i = 0; i < n; i++) {
            if (matrix[i][0] == 0) col0 = 0;
            for (int j = 1; j < m; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 1; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
            if (col0 == 0) matrix[i][0] = 0;
        }
    }
};

Java

class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        int col0 = 1;
        for (int i = 0; i < n; i++) {
            if (matrix[i][0] == 0) col0 = 0;
            for (int j = 1; j < m; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 1; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
            if (col0 == 0) matrix[i][0] = 0;
        }
    }
}

Python

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        n, m = len(matrix), len(matrix[0])
        col0 = 1
        for i in range(n):
            if matrix[i][0] == 0:
                col0 = 0
            for j in range(1, m):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, 0, -1):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
            if col0 == 0:
                matrix[i][0] = 0

C#

public class Solution {
    public void SetZeroes(int[][] matrix) {
        int n = matrix.Length, m = matrix[0].Length;
        int col0 = 1;
        for (int i = 0; i < n; i++) {
            if (matrix[i][0] == 0) col0 = 0;
            for (int j = 1; j < m; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 1; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
            if (col0 == 0) matrix[i][0] = 0;
        }
    }
}

Complexity Analysis

Time Complexity: O(m × n) – Each cell is visited twice (marking and updating).
Space Complexity: O(1) – No extra space is used beyond a constant flag.

Walkthrough Example

Input:

[[1, 2, 3],
 [4, 0, 6],
 [7, 8, 9]]

Step 1 – Mark:

matrix[1][1] == 0 → mark matrix[1][0] = 0, matrix[0][1] = 0

Step 2 – Update:

Cells in row 1 and column 1 are set to 0.