Set Matrix Zeroes medium

Problem Statement

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0. 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]]

Steps

The naive approach would iterate through the matrix, and whenever a 0 is found, iterate again to set the entire row and column to 0. This is inefficient (O(mnm) or O(mnn)). A better approach utilizes the first row and first column as markers to track whether a row or column needs to be zeroed.

1. First pass: Iterate through the matrix. If you find a 0, set the first element of its row (matrix[i][0]) and the first element of its column (matrix[0][j]) to 0. These first row and column elements act as flags.

2. Second pass: Iterate through the matrix except the first row and first column. If matrix[i][0] or matrix[0][j] is 0, set matrix[i][j] to 0.

3. Third pass (for handling the first row and column):

   • If matrix[0][0] is 0, set the entire first row to 0.
   • Iterate through the first column. If matrix[i][0] is 0, set the entire i-th row to 0.

Explanation

The key optimization is using the first row and column as space to store information about which rows and columns need to be zeroed. This avoids the need for extra space and reduces the time complexity significantly. The third pass handles the edge cases of the first row and column correctly.

Code

public class Solution {
    public void SetZeroes(int[][] matrix) {
        int m = matrix.Length;
        int n = matrix[0].Length;

        // First pass: Mark rows and columns with 0s
        bool firstRowZero = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) firstRowZero = true;
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Second pass: Set zeros based on flags
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Third pass: Handle first row and column
        if (matrix[0][0] == 0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

Complexity

• Time Complexity: O(mn) - We iterate through the matrix three times, each time taking O(mn) time.
• Space Complexity: O(1) - We are modifying the matrix in place and not using any additional data structures that scale with the input size.