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:

$$ \begin{bmatrix} 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 \end{bmatrix} \Longrightarrow \begin{bmatrix} 0 & \colorbox{orange} 0 & 0 & 0 & \colorbox{orange} 0 \\ \colorbox{orange} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & \colorbox{orange} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \end{bmatrix} $$

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:

$$ \begin{bmatrix} 0 & 1 & 2 & 0 \\ 3 & 4 & 5 & 2 \\ 1 & 3 & 1 & 5 \end{bmatrix} \Longrightarrow \begin{bmatrix} \colorbox{orange} 0 & 0 & 0 & \colorbox{orange} 0 \\ 0 & 4 & 5 & 0 \\ 0 & 3 & 1 & 0 \end{bmatrix} $$

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

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

public static void setZero(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 2 - 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

boolean[] rowBooleanVectors = new boolean[matrix.length];
boolean[] colBooleanVectors = new boolean[matrix[0].length];
for (int i = 0; i < matrix.length; ++i) {
    for (int j = 0; j < matrix[0].length; ++j) {
        if (matrix[i][j] == 0) {
            rowBooleanVectors[i] = true;
            colBooleanVectors[j] = true;
        }
    }
}

for (int i = 0; i < matrix.length; ++i) {
    for (int j = 0; j < matrix[0].length; ++j) {
        if (rowBooleanVectors[i] || colBooleanVectors[j])
            matrix[i][j] = 0;
    }
}

Complexity

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

Method 3 - Using first row and column as boolean array

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 rowBooleanArray[] and colBooleanArray[] 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.

Psuedocode

 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
65

public void setZeroes(int[][] matrix) {
	 if (matrix.length <= 0) {
		return;
	}
	
	int m = matrix.length;
	int n = matrix[0].length;

	boolean firstRowZero = false;
	boolean firstColZero = false;

	for (int j = 0; j < n; j++) {
		if (matrix[0][j] == 0) {
			firstRowZero = true;
			break;
		}
	}
	for (int i = 0; i < m; i++) {
		if (matrix[i][0] == 0) {
			firstColZero = true;
			break;
		}
	}

	// Now use first row and first col to record the values
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			if (matrix[i][j] == 0) {
				// set zero flag on the first row/col
				matrix[0][j] = 0;
				matrix[i][0] = 0;
			}
		}
	}

	// Update Inner matrix values based on respective row and col
	for(int i = 1; i < m ;i++) {
		for(int j = 1; j < n; j++) {
			if(matrix[i][0] == 0 || matrix[0][j] == 0) {
				matrix[i][j] = 0;
			}
		}
	}

	// set zero based on zero flag
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			if (matrix[0][j] == 0 || matrix[i][0] == 0) {
				matrix[i][j] = 0;
			}
		}
	}

	if (firstRowZero) {
		for (int j = 0; j < n; j++) {
			matrix[0][j] = 0;
		}
	}

	if (firstColZero) {
		for (int i = 0; i < m; i++) {
			matrix[i][0] = 0;
		}
	}
}

Complexity

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

Method 3 - 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.