LeetCode 73: Set Matrix Zeroes Solution

Master LeetCode problem 73 (Set Matrix Zeroes), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

73. Set Matrix Zeroes

Medium

Array Hash Table Matrix

Problem Explanation

Explanation

To solve this problem in constant space, we can utilize the first row and first column of the matrix to keep track of which rows and columns need to be zeroed out. We can use two additional boolean variables to track if the first row and first column themselves need to be zeroed out.

Here's the step-by-step algorithm:

Scan the first row and first column of the matrix to check if they need to be zeroed out. Store this information in two boolean variables.
Iterate through the rest of the matrix, if an element is 0, set the corresponding element in the first row and first column to 0.
Iterate through the first row and first column and zero out the entire row or column if the corresponding element is 0.
Finally, zero out the matrix based on the information stored in the first row and first column.

The time complexity of this algorithm is O(m * n) where m is the number of rows and n is the number of columns in the matrix. The space complexity is O(1) as we are using constant extra space.

Solution Code

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean firstRowZero = false;
        boolean firstColZero = false;
        
        // Check if first row needs to be zeroed out
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }
        
        // Check if first column needs to be zeroed out
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }
        
        // Mark zeros in first row and column
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        // Zero out the matrix based on first row and first column
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // Zero out first row if needed
        if (firstRowZero) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[0][j] = 0;
            }
        }
        
        // Zero out first column if needed
        if (firstColZero) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 73 (Set Matrix Zeroes)?

This page provides optimized solutions for LeetCode problem 73 (Set Matrix Zeroes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 73 (Set Matrix Zeroes)?

The time complexity for LeetCode 73 (Set Matrix Zeroes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 73 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 73 in Java, C++, or Python.

Back to LeetCode Solutions