# GIVEN AN M X N MATRIX OF 0S AND 1S, IF AN ELEMENT IS 0, SET ITS ENTIRE ROW AND COLUMN TO 0.

By: Saurav

2018-01-09 02:57:00 UTC

Do it in place.

Example

Given array A as

1 0 1
1 1 1
1 1 1
On returning, the array A should be :

0 0 0
1 0 1
1 0 1

InterviewBit

This problem looks easy but there is a trick. You need to spot the trick/problem.

For the given test case, suppose we iterate through the array and if we find a 0, we make all the elements in the row and column 0. Lets see what happens with such a code.

```def set_matrix_zero(arr)
m = arr.size
n = arr[0].size

return arr if m == 0 or m == 0

(0..m-1).each do |i|
(0..n-1).each do |j|
if arr[i][j] == 0
change_row_column(arr, i,j, m, n)
end
end
end

return arr

end

def change_row_column(arr, i,j, m, n)
(0..n-1).each do |k|
arr[i][k] = 0
end

(0..m-1).each do |k|
arr[k][j] = 0
end

return arr

end```

```set_matrix_zero([[0,0,1],[1,1,1],[1,1,1]]) gives [[0,0,0],[0,0,0],[0,0,0]]

```

As you noticed, even if one 0 is present in the array, it will make all the elements 0 successively. It's like a BFS(Breadth First Search) which alters the array to create neighbors no matter what actual value they have. And that will be like a flood all over the array.

To solve that problem, we need a buffer value like -1 or -2 or anything which is not 0 or 1 to replace all 1s. This doesn't run the flood filling because it won't find 0 for the neighbors. keep in mind not to replace the 0s. Lets take a look

```def set_matrix_zero(arr)
m = arr.size
n = arr[0].size

return arr if m == 0 or m == 0

(0..m-1).each do |i|
(0..n-1).each do |j|
if arr[i][j] == 0
change_row_column(arr, i,j, m, n)
end
end
end

(0..m-1).each do |i|
(0..n-1).each do |j|
if arr[i][j] == -1
arr[i][j] = 0
end
end
end

return arr

end

def change_row_column(arr, i,j, m, n)
(0..n-1).each do |k|
arr[i][k] = -1 unless arr[i][k] == 0
end

(0..m-1).each do |k|
arr[k][j] = -1 unless arr[k][j] == 0
end

return arr

end```

Running the tests:

```p set_matrix_zero([[0,0,1],[1,1,1],[1,1,1]]) == [[0, 0, 0], [0, 0, 1], [0, 0, 1]]
p set_matrix_zero([[0,1],[1,1]]) == [[0, 0], [0, 1]]
p set_matrix_zero([[1,0,1],[1,1,1],[1,1,1]]) == [[0, 0, 0], [1, 0, 1], [1, 0, 1]]
```

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)