Problem

Given an m x n matrix of 0s and 1s, provide an algorithm such that if an element is 0, its entire row and  column is set to 0

OR

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.

You must do it in place.

Follow Up:

     Can you do it in one pass?

Examples

Example 1:

$$ \Huge \begin{array}{|c|c|c|c|c|} \hline 1 & \colorbox{orange} 0 & 1 & 1 & \colorbox{orange} 0 \\ \hline \colorbox{orange} 0 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 \\ \hline 1 & \colorbox{orange} 0 & 1 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 \\ \hline \end{array} \Longrightarrow \begin{array}{|c|c|c|c|c|} \hline \colorbox{yellow} 0 & \colorbox{orange} 0 & \colorbox{yellow} 0 & \colorbox{yellow} 0 & \colorbox{orange} 0 \\ \hline \colorbox{orange} 0 & \colorbox{yellow} 0 & \colorbox{yellow} 0 & \colorbox{yellow} 0 & \colorbox{yellow} 0 \\ \hline \colorbox{yellow} 0 & \colorbox{yellow} 0 & 1 & 1 & \colorbox{yellow} 0 \\ \hline \colorbox{yellow} 0 & \colorbox{orange} 0 & \colorbox{yellow} 0 & \colorbox{yellow} 0 & \colorbox{yellow} 0 \\ \hline \colorbox{yellow} 0 & \colorbox{yellow} 0 & 1 & 1 & \colorbox{yellow} 0 \\ \hline \end{array} $$

1
2

Input : matrix =[[1,0,1,1,0],[0,1,1,1,1],[1,1,1,1,1], [1,0,1,1,1],[1,1,1,1,1]]
Output: [ [0,0,0,0,0],[0,0,0,0,0],[0,0,1,1,0],[0,0,0,0,0], [0,0,1,1,0]]

Example 2:

$$ \Huge \begin{array}{|c|c|c|c|} \hline \colorbox{orange} 0 & 1 & 2 & \colorbox{orange} 0 \\ \hline 3 & 4 & 5 & 2 \\ \hline 1 & 3 & 1 & 5 \\ \hline \end{array} \Longrightarrow \begin{array}{|c|c|c|c|} \hline \colorbox{orange} 0 & \colorbox{yellow} 0 & \colorbox{yellow} 0 & \colorbox{orange} 0 \\ \hline \colorbox{yellow} 0 & 4 & 5 & \colorbox{yellow} 0 \\ \hline \colorbox{yellow} 0 & 3 & 1 & \colorbox{yellow} 0 \\ \hline \end{array} $$

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

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Naive - Using copy matrix

In the naive approach, we solve the problem by creating a copy of the input matrix. This duplicate is used to track which rows and columns need modification. By using a separate matrix, we avoid overwriting the original matrix during the process.

Approach

  1. Create a Copy Matrix:
    • First, create a new matrix (let’s call it copyMatrix) of the same size as the input matrix, and copy all values from the input matrix into this new matrix.
  2. Iterate and Record:
    • Traverse through the original matrix and identify any element with the value 0.
    • For each 0 found in the original matrix, set its corresponding row and column in the copyMatrix to 0.
  3. Update Original Matrix:
    • Once the entire copyMatrix is updated, use its values to overwrite the original matrix.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;

        // Step 1: Create a copy of the matrix
        int[][] copyMatrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                copyMatrix[i][j] = matrix[i][j];
            }
        }

        // Step 2: Traverse the original matrix and mark rows/columns in the copy
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    // Set the entire row to 0
                    for (int k = 0; k < n; k++) {
                        copyMatrix[i][k] = 0;
                    }
                    // Set the entire column to 0
                    for (int k = 0; k < m; k++) {
                        copyMatrix[k][j] = 0;
                    }
                }
            }
        }

        // Step 3: Copy results back to the original matrix
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = copyMatrix[i][j];
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        m, n = len(matrix), len(matrix[0])

        # Step 1: Create a copy of the matrix
        copy_matrix = [row[:] for row in matrix]

        # Step 2: Traverse the original matrix and mark rows/columns in the copy
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    # Set the entire row to 0
                    for k in range(n):
                        copy_matrix[i][k] = 0
                    # Set the entire column to 0
                    for k in range(m):
                        copy_matrix[k][j] = 0

        # Step 3: Copy results back to the original matrix
        for i in range(m):
            for j in range(n):
                matrix[i][j] = copy_matrix[i][j]

Complexity

  • ⏰ Time complexity: O(m*n(m + n)).
    • Copy Matrix Creation: O(m * n) where m is the number of rows and n is the number of columns.
    • Traversal and Marking: For each element in the matrix, traverse its corresponding row and column, leading to a worst-case time complexity of O(m * n * (m + n)) for larger matrices. Thus, time complexity is O(m * n * (m + n)).
  • 🧺 Space complexity: O(m*n) as the additional copyMatrix requires O(m * n) space.

Method 2 - Using the set as Extra Space

In this approach we can do :

  1. Scan the matrix, store the numbers of rows and columns that will be set to zero to two sets
  2. Iterate through those two sets and set corresponding row and col to zeros.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
	public void setZeroes(int[][] matrix) {
	    Set <Integer> rowToClear = new HashSet <>();
	    Set <Integer> colToClear = new HashSet <>();
	    for (int i = 0; i < matrix.length; ++i) {
	        for (int j = 0; j < matrix[0].length; ++j) {
	            if (matrix[i][j] == 0) {
	                rowToClear.add(i);
	                colToClear.add(j);
	            }
	        }
	    }
	
	    for (Integer row: rowToClear) {
	        for (int j = 0; j < matrix[row].length; ++j) {
	            matrix[row][j] = 0;
	        }
	    }
	
	    for (Integer col: colToClear) {
	        for (int i = 0; i < matrix.length; ++i) {
	            matrix[i][col] = 0;
	        }
	    }
	}
}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(m+n)

Method 3 - Using boolean array as extra space

Also, as SET takes more space, rather than using SET, we can use a simple boolean arrays.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;

        // Step 1: Initialize rowMarker and colMarker
        boolean[] rowMarker = new boolean[m];
        boolean[] colMarker = new boolean[n];

        // Step 2: Traverse the matrix and set markers
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rowMarker[i] = true; // Mark row
                    colMarker[j] = true; // Mark column
                }
            }
        }

        // Step 3: Update rows based on rowMarker
        for (int i = 0; i < m; i++) {
            if (rowMarker[i]) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Step 4: Update columns based on colMarker
        for (int j = 0; j < n; j++) {
            if (colMarker[j]) {
                for (int i = 0; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        m, n = len(matrix), len(matrix[0])

        # Step 1: Initialize rowMarker and colMarker
        row_marker = [False] * m
        col_marker = [False] * n

        # Step 2: Traverse the matrix and set markers
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row_marker[i] = True  # Mark row
                    col_marker[j] = True  # Mark column

        # Step 3: Update rows based on rowMarker
        for i in range(m):
            if row_marker[i]:
                for j in range(n):
                    matrix[i][j] = 0

        # Step 4: Update columns based on colMarker
        for j in range(n):
            if col_marker[j]:
                for i in range(m):
                    matrix[i][j] = 0

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(m+n)

Method 4 - Using first row and column as boolean array and use 2 flags

This method is a space optimized version of above method 1. This method uses the first row and first column of the input matrix in place of the auxiliary arrays rowMarker and colMarker of method 1.

So what we do is: first take care of first row and column and store the info about these two in two flag variables rowFlag and colFlag. Once we have this info, we can use first row and first column as auxiliary.

We now need 2 passes.

  • I use first column and first row as markers to know where are rows/cols with only 1’s. Then, there are 2 variables r and c to remember if first row/column are all 1’s also. So the first pass sets the markers and resets the rest to 0’s.
  • The second pass sets 1 in places where rows and cols where marked to be 1, and resets 1st line/col depending on r and c.

Now apply method 1 for submatrix (matrix excluding first row and first column) of size (M-1)*(N-1):

  1. Scan the first row and set a variable rowFlag to indicate whether we need to set all 0s in first row or not.
  2. Scan the first column and set a variable colFlag to indicate whether we need to set all 0s in first column or not.
  3. Use first row and first column as the auxiliary arrays row[] and col[] respectively, consider the matrix as submatrix starting from second row and second column and apply method 1.
  4. Finally, using rowFlag and colFlag, update first row and first column if needed.

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

N = matrix.length;
M = matrix[0].length;

// pass 1

// 1 rst line/column
int c = 1
for (int i = 0; i < N; ++i) {
    c &= matrix[i][0]
}

r = 1
for (int j = 0; j < M; ++j) {
    r &= matrix[0][i]
}

// other line/cols
// use line1, col1 to keep only those with 1
for (int i = 1; i < N; ++i) { //start iterating with 1
    for (int j = 1; j < M; ++j) {
        if (matrix[i][j] == 0) {
            matrix[0][j] = 0
            matrix[i][0] = 0
        } else {
            matrix[i][j] = 0
        }
    }
}
// pass 2

// if line1 and col1 are ones: it is 1
for (int i = 1; i < N; ++i) {
    for (int j = 1; j < M; ++j) {
        if (matrix[i][0] & matrix[0][j] == 1) {
            matrix[i][j] = 1
        }
    }
}

// 1rst row and col: reset if 0
if (l == 0) {
    for (int i = 0; i < N; ++i) {
        matrix[i][0] = 0
    }
}
if (c == 0) {
    for (int j = 1; j < M; ++j) {
        matrix[0][j] = 0
    }
}

print(matrix);

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

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

        // Step 1: Check if the first row has any zero
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowHasZero = true;
                break;
            }
        }

        // Step 1: Check if the first column has any zero
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }

        // Step 2: Use first row and column as markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0; // Mark row
                    matrix[0][j] = 0; // Mark column
                }
            }
        }

        // Step 3: Update rows based on markers in the first column
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Step 4: Update columns based on markers in the first row
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 1; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Step 5: Handle first row
        if (firstRowHasZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        // Step 5: Handle first column
        if (firstColHasZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        first_row_has_zero = False
        first_col_has_zero = False

        # Step 1: Check if the first row has any zero
        for j in range(n):
            if matrix[0][j] == 0:
                first_row_has_zero = True
                break

        # Step 1: Check if the first column has any zero
        for i in range(m):
            if matrix[i][0] == 0:
                first_col_has_zero = True
                break

        # Step 2: Use first row and column as markers
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0  # Mark row
                    matrix[0][j] = 0  # Mark column

        # Step 3: Update rows based on markers in the first column
        for i in range(1, m):
            if matrix[i][0] == 0:
                for j in range(1, n):
                    matrix[i][j] = 0

        # Step 4: Update columns based on markers in the first row
        for j in range(1, n):
            if matrix[0][j] == 0:
                for i in range(1, m):
                    matrix[i][j] = 0

        # Step 5: Handle first row
        if first_row_has_zero:
            for j in range(n):
                matrix[0][j] = 0

        # Step 5: Handle first column
        if first_col_has_zero:
            for i in range(m):
                matrix[i][0] = 0

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(1)

Method 5 - Using just 1 flag

Intuition

While the two-flag approach works perfectly, we realise that the two flags (firstRowHasZero and isFirstColZero) add unnecessary complexity.

By assigning the marker array for rows to the first column and for columns to the first row, we can store all necessary information for the sub-matrix. However, this creates ambiguity at the common cell (0, 0) (matrix[0][0]), where it’s unclear whether it belongs to the row marker or column marker.

Resolving Ambiguity at (0, 0)
Scenario 1: Zero in the First Row

Consider the matrix where the 0 exists only in the first row:

1
2
3

[[1, 1, 0],
  [1, 1, 1],
  [1, 1, 1]]

The 0 at matrix[0][2] would cause us to set the marker at matrix[0][0] to 0, representing the row marker.

Scenario 2: Zero in the First Column

Consider a different matrix where the 0 exists only in the first column:

1
2
3

[[1, 1, 1],
  [1, 1, 1],
  [0, 1, 1]]

The 0 at matrix[2][0] would also cause us to set matrix[0][0] to 0, representing the column marker.

To resolve this ambiguity, we assign (0, 0) (matrix[0][0]) exclusively to the row marker array and eliminate the need for the firstRowZero flag, retaining only the firstColZero flag.

To optimise further, we leverage the matrix itself as a marker and use only one flag (isFirstColZero). This flag handles the first column separately, avoiding ambiguity over the shared marker cell matrix[0][0].

How Do We Resolve This?

So, to avoid this ambiguity,

  1. The first row (using matrix[0][j] markers) can represent all column markers.
  2. The first column (using matrix[i][0] markers) can represent all row markers.
  3. The common cell matrix[0][0] represents row markers by default, and the separate flag (isFirstColZero) efficiently handles the first column.

Approach

  1. Step 1: Check the First Column:
    • Start by scanning the first column (matrix[i][0]) to check if it contains a 0.
    • If any cell in the first column is 0, set the flag isFirstColZero = True.
  2. Step 2: Mark Rows and Columns Using the Matrix Itself:
    • Traverse the rest of the matrix (excluding the first row and the first column).
    • If a cell matrix[i][j] is 0:
      • Mark its row by setting matrix[i][0] = 0.
      • Mark its column by setting matrix[0][j] = 0.
    • These markers in the first row and column will later be used to update the matrix.
  3. Step 3: Update Rows and Columns:
    • Update Rows:
      • Traverse all rows starting from 1 onwards.
      • For any row i, if the marker in the first column (matrix[i][0]) is 0, set all elements in that row to 0.
    • Update Columns:
      • Traverse all columns starting from 1 onwards.
      • For any column j, if the marker in the first row (matrix[0][j]) is 0, set all elements in that column to 0.
  4. Step 4: Handle the First Row and First Column:
    • Handle the First Row:
      • If the marker at matrix[0][0] is 0, set all elements in the first row to 0.
    • Handle the First Column:
      • If isFirstColZero = True, set all elements in the first column to 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean isFirstColZero = false;

        // Step 1: Check the first column for any zero
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                isFirstColZero = true;
                break;
            }
        }

        // Step 2: Use the matrix itself to mark rows and columns
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;  // Mark the row
                    matrix[0][j] = 0;  // Mark the column
                }
            }
        }

        // Step 3: Update rows using the markers in the first column
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Step 4: Update columns using the markers in the first row
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 0; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Step 5: Handle the first row
        if (matrix[0][0] == 0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        // Step 5: Handle the first column
        if (isFirstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        is_first_col_zero = False

        # Step 1: Check the first column for any zero
        for i in range(m):
            if matrix[i][0] == 0:
                is_first_col_zero = True
                break

        # Step 2: Use the matrix itself to mark rows and columns
        for i in range(m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0  # Mark the row
                    matrix[0][j] = 0  # Mark the column

        # Step 3: Update rows using the markers in the first column
        for i in range(1, m):
            if matrix[i][0] == 0:
                for j in range(1, n):
                    matrix[i][j] = 0

        # Step 4: Update columns using the markers in the first row
        for j in range(1, n):
            if matrix[0][j] == 0:
                for i in range(m):
                    matrix[i][j] = 0

        # Step 5: Handle the first row
        if matrix[0][0] == 0:
            for j in range(n):
                matrix[0][j] = 0

        # Step 5: Handle the first column
        if is_first_col_zero:
            for i in range(m):
                matrix[i][0] = 0

Method 6 - Doing it in One Pass

So the idea is to use the values in the last row/column as a flag to indicate whether all of the values in the corresponding column/row are 1s. Using a Zig Zag scan through the entire matrix EXCEPT the final row/column. At each element, you set the value in the final row/column as to the logical AND of itself with the value in the current element. In other words, if you hit a 0, the final row/column will be set to 0. If you hit a 1, the value in the final row/column will be 1 only if it was 1 already. In any case set the current element to 0.

When you’ve finished, your final row/column should have 1s iff the corresponding column/row was filled with 1s.

Do a linear scan through the final row and column and looking for 1s. Set 1s in the corresponding elements in body of the matrix where the final row and column are both 1s.

Coding it will be tricky to avoid off-by-one errors etc but it should work in one pass.