Set Matrix Zeroes: Efficient In-Place Modification

The "Set Matrix Zeroes" problem involves modifying a matrix in-place, setting entire rows and columns to zero where any element in them is zero.

Problem Statement

Given an m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example

• Input: Matrix [ [1,1,1], [1,0,1], [1,1,1] ]

• Output: [ [1,0,1], [0,0,0], [1,0,1] ]

Solution Approach - Space Optimized

Breaking Down the Solution

• Mark Zeroes: Iterate through the matrix, marking the first cell of each row and column that contains a zero.
• Set Rows and Columns: Use the marks to set entire rows and columns to zero.
• Handle First Row and Column: Special handling for the first row and column to avoid overriding the marks.

Conclusion

The Set Matrix Zeroes problem is a valuable exercise in in-place array manipulation. It requires careful consideration to avoid unintended side effects while modifying the matrix.

The algorithm achieves constant space complexity (O(1)) by using the first row and the first column of the matrix itself to store information about which rows and columns should be zeroed.

Here’s a breakdown of how this is achieved:

First Pass: Iterate through the matrix and use the first cell of each row and column to mark whether that row or column should be set to zero. This requires two special checks:

Determine if the first row should be set to zero based on the cells in the first row. Determine if the first column should be set to zero based on the cells in the first column. Second Pass: Use the marks in the first row and first column to set the appropriate rows and columns to zero. Skip the first row and first column in this pass.

Final Step: Based on the checks from the first step, set the first row and/or first column to zero if needed.

This approach only uses a constant amount of additional space (for variables like isCol and loop counters) and modifies the matrix in place.

Rust Solution

set_zeroes takes &mut [Vec<i32>], a mutable slice of rows, so main keeps ownership and hands over &mut m; every matrix[i][j] = 0 write then mutates the caller's data in place with no return value. Emptiness is tested with the is_empty() method — matrix.is_empty() and matrix[0].is_empty() — rather than a length comparison, and the passes walk half-open ranges such as 0..r and 1..c, where 1..c skips the marker column. The element type is fixed to i32 by Vec<i32>, and main prints the nested vector via the {:?} debug formatter in println!.

Go Solution

Go passes matrix [][]int by value, but a slice is a header over a shared backing array, so the matrix[i][j] = 0 writes are visible to the caller and main invokes setZeroes(m) with no pointer or &. Bounds come from the len builtin through the multiple assignment r, c := len(matrix), len(matrix[0]), and the empty-input guard is a bare return from the void function. Both passes are classic three-clause for i := 0; i < r; i++ loops — Go's only loop form — and fmt.Println(m) prints the nested [][]int.