73. Set Matrix Zeroes

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

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input: 
[
  [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]
]

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?

---

Intuition

We cannot flip every cell in row or column to zero when we encounter a zero, this would mean we potentially end up with a matrix of all zeros. We need to identify which cells are zero in the original matrix, and then use that information

1. O(m*n) solution - additional array which stores the right cell to flip bits on, and then parse that to set bits on original matrix

2. O(m + n) solution - 2 arrays to store which row, which column needs to switched to zero, then iterate through the original matrix flipping all columns in respective row, or all rows in respective column

3. In place - set first col of each row, or 1st row of each col as 0 if the cell is zero, save if the first row or col itself is zero. Traverse from 1 to R, 1 to C, mark cell to 0 if first col or first row cell is zero. Third traversal set the first col,  first row to zero if it was saved in step 1

---