73. Set Matrix Zeroes

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.

View Leetcode Problem

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;
            }
        }
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.