algoadvance

Leetcode 3033. Modify the Matrix

Problem Statement

You are given an ( m \times n ) integer matrix. If a cell has the value 0, you should set all the cells in its row and column to 0. Implement a function to perform this operation without using extra space for another matrix.

Example:

Input:

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

Output:

[
 [1, 0, 3],
 [0, 0, 0],
 [7, 0, 9]
]

Clarifying Questions

  1. Can the matrix contain negative numbers?
    • Yes, the matrix can contain negative numbers.
  2. Can the matrix be empty?
    • Yes, the matrix can be empty. Handle this as a special case.
  3. Is it required to modify the input matrix in place?
    • Yes, you need to modify the matrix in place without using extra space for another matrix.

Strategy

  1. Identify the Cells with Zeros: Iterate through the matrix to identify the cells that contain 0. Use the first row and the first column of the matrix to store this information instead of using extra space.
  2. Mark the Rows and Columns: Use the first row to mark which columns need to be zeroed and the first column to mark which rows need to be zeroed.
  3. Zero Out the Marked Rows and Columns: Traverse the matrix again using the markers in the first row and first column to set the appropriate rows and columns to zero.
  4. Handle the Edge Case for First Row and First Column: Since the first row and first column are used as markers, handle them separately to ensure they are zeroed out if necessary.

Steps:

  1. Use the first row and column as markers.
  2. Traverse the matrix to mark the rows and columns that need to be zeroed.
  3. Use these markers to set the required rows and columns to zero.
  4. Special handling for the first row and first column if they originally contained any zeros.

Code

Here’s the Java code that performs the above-stated strategy:

public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean firstRowZero = false;
        boolean firstColZero = false;
        
        // Checking if the first row needs to be zeroed
        for (int j = 0; j < cols; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }
        
        // Checking if the first column needs to be zeroed
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }
        
        // Use first row and column to mark zeros
        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;
                }
            }
        }

        // Zero out cells based on the markers in the first row and column
        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;
                }
            }
        }
        
        // Zero out the first row if needed
        if (firstRowZero) {
            for (int j = 0; j < cols; j++) {
                matrix[0][j] = 0;
            }
        }

        // Zero out the first column if needed
        if (firstColZero) {
            for (int i = 0; i < rows; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI