Set matrix zeroes#

Levels: level-3

Data structures: array

Practice Link#

Description#

Given a m x n matrix, if an element is 0, set its entire row and column to 0.
Do it in-place.

Examples#

 1Input:
 2[
 3  [1,1,1],
 4  [1,0,1],
 5  [1,1,1]
 6]
 7Output:
 8[
 9  [1,0,1],
10  [0,0,0],
11  [1,0,1]
12]

 1Input:
 2[
 3  [0,1,2,0],
 4  [3,4,5,2],
 5  [1,3,1,5]
 6]
 7Output:
 8[
 9  [0,0,0,0],
10  [0,4,5,0],
11  [0,3,1,0]
12]

Follow up#

A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Python Solution#

 1class Solution:
 2    # @param {integer[][]} matrix
 3    # @return {void} Do not return anything, modify matrix in-place instead.
 4    def setZeroes(self, matrix):
 5        m = len(matrix)
 6        if m == 0:
 7            return
 8        n = len(matrix[0])
 9
10        row_zero = False
11        for i in range(m):
12            if matrix[i][0] == 0:
13                row_zero = True
14        col_zero = False
15        for j in range(n):
16            if matrix[0][j] == 0:
17                col_zero = True
18
19        for i in range(1, m):
20            for j in range(1, n):
21                if matrix[i][j] == 0:
22                    matrix[i][0] = 0
23                    matrix[0][j] = 0
24
25        for i in range(1, m):
26            if matrix[i][0] == 0:
27                for j in range(1, n):
28                    matrix[i][j] = 0
29
30        for j in range(1, n):
31            if matrix[0][j] == 0:
32                for i in range(1, m):
33                    matrix[i][j] = 0
34
35        if col_zero:
36            for j in range(n):
37                matrix[0][j] = 0
38        if row_zero:
39            for i in range(m):
40                matrix[i][0] = 0