73. Set Matrix Zeroes

MediumArrayHash TableMatrix
Leetcode Link

Problem Description

Given a 2D matrix of integers, the challenge is to modify the matrix such that if any cell contains the value 0, then all cells in the same row and column as that 0 are set to 0. The crucial requirement is that this transformation must be done 'in place,' which means you cannot use any additional memory to store large temporary data structures like a copy of the original matrix. The goal is to achieve the required transformation efficiently with respect to space.

Intuition

To solve this problem we need to track the rows and columns that must be set to 0 without using extra space for another matrix. We can use two boolean variables (i0 and j0) to keep track of whether the first row and the first column should be zeroed as they will serve as markers.

Here is an intuition for the solution approach:

  • If we find a 0 in any cell of the matrix, the row and column of that cell must be zeroed out. However, if we immediately reset all cells in the same row and column to 0, information about other 0s in those rows and columns could be lost.

  • To work around this, we can use the first cell of each row and column as a flag that indicates whether that entire row or column should be set to 0.

  • First, we check if the first row and first column should be zeroed by looking for any 0s and store this information in i0 for the first row, and j0 for the first column.

  • We iterate over the rest of the matrix (to avoid overriding i0 and j0 flags) and if we find a 0, we set the first cell of that row and column to 0. These markers will be used later to update the rows and columns.

  • After marking, we iterate over the matrix again, ignoring the first row and column, and update cells to 0 if their row or column marker is 0.

  • Finally, we use i0 and j0 to set the first row and column to 0 if needed.

This approach allows us to keep track of which rows and columns need to be zeroed without using additional space, hence giving us an in-place solution.

Solution Approach

The solution involves a few logical steps to minimize space complexity while ensuring the entire row and column are set to 0 for each 0 in the matrix. Here's a step-by-step breakdown:

  1. Initialization: We initialize two boolean variables i0 and j0. We use i0 to check if the first row needs to be set to 0 by iterating through the first row. Similarly, j0 is used to check if the first column needs to be set to 0 by iterating down the first column.

  2. Marking Rows and Columns: To preserve the information of where 0s are in the matrix without using extra space, we use the first row and column of the matrix itself. As we iterate through the matrix starting from element at (1,1), if a 0 is encountered at position (i,j), we mark the first element of row i (at position (i,0)) and the first element of column j (at position (0,j)) to 0.

    This way, we're using the matrix itself to keep track of rows and columns that will eventually be zeroed out. This clever trick avoids the need for additional data structures for marking purposes.

  3. Zeroing Rows and Columns: Having marked the rows and columns that need to be updated, we now iterate again through the matrix starting from element at (1,1) to m-1 x n-1. For any cell (i,j), we check if the first element of row i or the first element of column j is 0. If either is 0, this implies the current cell should also be 0, and we update it accordingly.

  4. Finalizing the First Row and Column: We check i0 and j0 from the first step. If i0 is true, we zero out the first row. Similarly, if j0 is true, we zero out the first column.

This in-place algorithm cleverly exploits the matrix's own first row and column to store the state needed to carry out the required transformation. This results in an O(1) space complexity as no additional storage proportional to the size of the matrix is needed, and the time complexity remains O(m x n) since we need to potentially look at all elements in the m x n matrix twice.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small 3x3 example matrix to illustrate the solution approach:

1Matrix before:
2[ [1, 2, 3],
3  [4, 0, 6],
4  [7, 8, 9] ]
  1. Initialization: i0 and j0 are initially set to false. We inspect the first row and first column to check for any 0s:

    • First row has no 0, thus i0 remains false.
    • First column also has no 0, so j0 remains false.
  2. Marking Rows and Columns: We start inspecting from (1,1):

    • No 0 at (1,1) — we move on.
    • We find a 0 at (1,3), so we mark the first element of row 1 (at position (1,0)) and the first element of column 3 (at position (0,3)) to 0.

    Now the matrix looks like this with markers set:

    1[ [1, 2, 0],  // Column 3 marked
    2  [0, 0, 6],  // Row 1 marked and the encountered 0
    3  [7, 8, 9] ]
  3. Zeroing Rows and Columns: With our markers set, we iterate through the matrix starting at (1,1) again and update according to markers:

    • Cell (1,1) stays 1 since neither the first element of row 1 nor column 1 is 0.
    • Cell (1,2) becomes 0 because the first element of column 2 (position (0,2)) is 0.
    • Continue through the matrix, checking the respective row or column start for a 0 marker.

    Updated matrix now looks like this:

    1[ [1, 0, 0],  // Column 3 zeroed out
    2  [0, 0, 0],  // Row 1 zeroed out
    3  [7, 0, 9] ] // Column 2 zeroed out because of the marker at (0,2)
  4. Finalizing the First Row and Column: Since i0 and j0 are both false, we know the first row and column can remain unchanged.

The final matrix after performing the in-place transformation looks like:

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

This demonstrates how the matrix is correctly transformed according to the problem's rules without using any additional space, as all the zeroing information is stored within the original matrix itself.

Solution Implementation

1class Solution:
2    def set_zeroes(self, matrix: List[List[int]]) -> None:
3        # Get the dimensions of the matrix
4        nrows, ncols = len(matrix), len(matrix[0])
5
6        # Determine if the first row has any zeroes
7        first_row_has_zero = any(value == 0 for value in matrix[0])
8        # Determine if the first column has any zeroes
9        first_col_has_zero = any(matrix[row][0] == 0 for row in range(nrows))
10
11        # Use the first row and column as flags for zeroes
12        # Start from 1 to avoid overwriting the first row and column flags
13        for row in range(1, nrows):
14            for col in range(1, ncols):
15                # If an element is zero, mark its row and column in the first row and column
16                if matrix[row][col] == 0:
17                    matrix[row][0] = matrix[0][col] = 0
18
19        # Set matrix elements to zero based on flags in the first row and column,
20        # ignoring the first row and column themselves
21        for row in range(1, nrows):
22            for col in range(1, ncols):
23                if matrix[row][0] == 0 or matrix[0][col] == 0:
24                    matrix[row][col] = 0
25
26        # If the first row had zeroes, set all elements in the first row to zero
27        if first_row_has_zero:
28            for col in range(ncols):
29                matrix[0][col] = 0
30
31        # If the first column had zeroes, set all elements in the first column to zero
32        if first_col_has_zero:
33            for row in range(nrows):
34                matrix[row][0] = 0
35
1class Solution {
2    public void setZeroes(int[][] matrix) {
3        int rowCount = matrix.length; // number of rows in the matrix
4        int colCount = matrix[0].length; // number of columns in the matrix
5        boolean firstRowHasZero = false; // flag to check if the first row contains a zero
6        boolean firstColHasZero = false; // flag to check if the first column contains a zero
7
8        // Check if the first row has any zeros
9        for (int col = 0; col < colCount; ++col) {
10            if (matrix[0][col] == 0) {
11                firstRowHasZero = true;
12                break;
13            }
14        }
15
16        // Check if the first column has any zeros
17        for (int row = 0; row < rowCount; ++row) {
18            if (matrix[row][0] == 0) {
19                firstColHasZero = true;
20                break;
21            }
22        }
23
24        // Use the first row and column as markers.
25        // Set matrix[i][0] and matrix[0][j] to 0 if matrix[i][j] is 0
26        for (int row = 1; row < rowCount; ++row) {
27            for (int col = 1; col < colCount; ++col) {
28                if (matrix[row][col] == 0) {
29                    matrix[row][0] = 0;
30                    matrix[0][col] = 0;
31                }
32            }
33        }
34
35        // Iterate over the matrix again using the first row and column as reference,
36        // and set the elements to 0 accordingly.
37        for (int row = 1; row < rowCount; ++row) {
38            for (int col = 1; col < colCount; ++col) {
39                if (matrix[row][0] == 0 || matrix[0][col] == 0) {
40                    matrix[row][col] = 0;
41                }
42            }
43        }
44
45        // Nullify the first row if needed
46        if (firstRowHasZero) {
47            for (int col = 0; col < colCount; ++col) {
48                matrix[0][col] = 0;
49            }
50        }
51
52        // Nullify the first column if needed
53        if (firstColHasZero) {
54            for (int row = 0; row < rowCount; ++row) {
55                matrix[row][0] = 0;
56            }
57        }
58    }
59}
60
1class Solution {
2public:
3    void setZeroes(vector<vector<int>>& matrix) {
4        int rowCount = matrix.size(), colCount = matrix[0].size();
5        bool firstRowHasZero = false, firstColHasZero = false;
6
7        // Check if the first row has a zero
8        for (int col = 0; col < colCount; ++col) {
9            if (matrix[0][col] == 0) {
10                firstRowHasZero = true;
11                break;
12            }
13        }
14
15        // Check if the first column has a zero
16        for (int row = 0; row < rowCount; ++row) {
17            if (matrix[row][0] == 0) {
18                firstColHasZero = true;
19                break;
20            }
21        }
22
23        // Use first row and column as markers, set matrix[i][0] and matrix[0][j] to 0 if matrix[i][j] is 0
24        for (int row = 1; row < rowCount; ++row) {
25            for (int col = 1; col < colCount; ++col) {
26                if (matrix[row][col] == 0) {
27                    matrix[row][0] = 0;
28                    matrix[0][col] = 0;
29                }
30            }
31        }
32
33        // Iterate over the matrix, set elements to 0 if their row or column marker is 0
34        for (int row = 1; row < rowCount; ++row) {
35            for (int col = 1; col < colCount; ++col) {
36                if (matrix[row][0] == 0 || matrix[0][col] == 0) {
37                    matrix[row][col] = 0;
38                }
39            }
40        }
41
42        // If the first row had zero, set all elements in the first row to 0
43        if (firstRowHasZero) {
44            for (int col = 0; col < colCount; ++col) {
45                matrix[0][col] = 0;
46            }
47        }
48
49        // If the first column had zero, set all elements in the first column to 0
50        if (firstColHasZero) {
51            for (int row = 0; row < rowCount; ++row) {
52                matrix[row][0] = 0;
53            }
54        }
55    }
56};
57
1/**
2 * Modifies a given matrix by setting entire rows and columns to zero if an element in them is zero.
3 * Operates in-place.
4 * @param {number[][]} matrix - A 2D array of numbers to be modified.
5 */
6function setZeroes(matrix: number[][]): void {
7    // Dimensions of the matrix
8    const rowCount = matrix.length;
9    const colCount = matrix[0].length;
10
11    // Flags indicating if the first row/column contains a zero
12    const isFirstRowZero = matrix[0].includes(0);
13    const isFirstColZero = matrix.some(row => row[0] === 0);
14
15    // Use first row/column as markers for zero rows/columns.
16    for (let row = 1; row < rowCount; ++row) {
17        for (let col = 1; col < colCount; ++col) {
18            if (matrix[row][col] === 0) {
19                // Mark the respective first row and column cell
20                matrix[row][0] = 0;
21                matrix[0][col] = 0;
22            }
23        }
24    }
25
26    // Set matrix cells to zero based on the marks
27    for (let row = 1; row < rowCount; ++row) {
28        for (let col = 1; col < colCount; ++col) {
29            if (matrix[row][0] === 0 || matrix[0][col] === 0) {
30                matrix[row][col] = 0;
31            }
32        }
33    }
34
35    // If the first row needs to be set to zero
36    if (isFirstRowZero) {
37        for (let col = 0; col < colCount; col++) {
38            matrix[0][col] = 0;
39        }
40    }
41  
42    // If the first column needs to be set to zero
43    if (isFirstColZero) {
44        for (let row = 0; row < rowCount; row++) {
45            matrix[row][0] = 0;
46        }
47    }
48}
49

Time and Space Complexity

The given code has a time complexity of O(m * n) where m is the number of rows and n is the number of columns in the given matrix. This is because the algorithm visits each cell twice, once to mark the rows and columns that should be zeroed and once to actually set the zeros.

For space complexity, the algorithm is O(1) as it uses constant extra space regardless of the size of the matrix. This is achieved by using the first row and first column of the matrix to store flags indicating whether a row or column should be set to zero.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following shows the order of node visit in a Breadth-first Search?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄