algoadvance

Leetcode 73. Set Matrix Zeroes

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]]

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^31 <= matrix[i][j] <= 2^31 - 1

Follow-up:

• A straightforward solution using O(mn) space is probably a bad idea.
• Could you devise a constant O(1) space solution?

---

Clarifying Questions:

1. Can the input matrix contain only integers?
   • Yes, it only contains integers.
2. Do we need to consider only immediate zeros or all zeros present at the start of the operation?
   • All the zeros present at the beginning of the operation.
3. Do we need to handle any specific edge cases?
   • Ensure to handle matrices with only one row or one column, and the case where the entire matrix is filled with zeros.

---

Strategy

1. Initial Scan:
   • First, we’ll scan the matrix to mark rows and columns that need to be zeroed.
2. Marking:
   • Use the first row and first column to mark which rows and columns need to be zeroed. Use two additional flags to determine if the first row and first column should be zeroed.
3. Zero Matrix Update:
   • Iterate through the matrix again and use the marks to set the appropriate rows and columns to zero.
4. Edge Cases Handling:
   • Finally, use the flags to determine if the first row and the first column should be zeroed.

---

Code

public class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;

        // Determine if the first row or first column have any zeroes
        for (int r = 0; r < rows; r++) {
            if (matrix[r][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }
        
        for (int c = 0; c < cols; c++) {
            if (matrix[0][c] == 0) {
                firstRowHasZero = true;
                break;
            }
        }

        // Use first row and column to mark zero rows and cols
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                }
            }
        }

        // Zero out cells based on the markers
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                if (matrix[r][0] == 0 || matrix[0][c] == 0) {
                    matrix[r][c] = 0;
                }
            }
        }

        // Zero out first row if needed
        if (firstRowHasZero) {
            for (int c = 0; c < cols; c++) {
                matrix[0][c] = 0;
            }
        }

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

---

Time Complexity

The time complexity of this solution is O(m * n) because we essentially pass through the matrix a constant number of times:

• Once to determine if the first row/column have any zeroes.
• Once to mark which rows and columns should be zero.
• Once to set the zeroes according to the marks.
• Handling the first row/column if necessary adds a single linear pass each.

The space complexity is O(1) (constant space) aside from storing the input matrix, since we’re only using a few additional boolean variables.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?