Set matrix to zero-coding question asked by Atlassian, Intuit

Problem statement:

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.

Input Format:

Matrix

Output Format:

Matrix with rows and columns having an element zero set to zero.

Sample Input 1:

matrix = [[1,1,1],[1,0,1],[1,1,1]]

Sample Output 1:

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

Sample Input 2:

matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Sample Output 2:

[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraint:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2³¹ <= matrix[i][j] <= 2³¹ — 1

Approach:

If any cell of the matrix has a zero we can record its row and column number. All the cells of this recorded row and column can be marked zero in the next iteration.

We make a pass over our original array and look for zero entries.If we find that an entry at [i, j] is 0, then we need to record somewhere the row i and column j.So, we use two sets, one for the rows and one for the columns.

if cell[i][j] == 0 { row_set.add(i) column_set.add(j) }

Finally, we iterate over the original matrix. For every cell we check if the row r or column c had been marked earlier. If any of them was marked, we set the value in the cell to 0.

if r in row_set or c in column_set { cell[r][c] = 0 }

Time complexity:0(m*n)

Space complexity: O(m+n)

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.