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 :)