73. Set Matrix Zeroes

Description: 

https://leetcode.com/problems/set-matrix-zeroes/

https://leetcode.com/problems/set-matrix-zeroes/

In the m * n matrix, there are serveral values. If the value is 0, than we should change the entire row value and column value as "0".

Before we do actual coding, let's think about the solution we can easily think. If we should check the entire matrix by brute force or whatever. It's gonna have O(mn) time solution.

If we make another matrix, and revise the value, then it is gonna have O(mn) space complexity(make one more matrix).

However, O(mn) is bad idea for this problem(straightfoward solution).

The problem requires O(1) soltuion which is a constant space soltuion.

Solution(Intuition, not answer):

Intution Solution

First, we set the variable M and N following matrix. Then, we made other two array(which is row and cols).

Here is the issue. If we make the other two arrays, that's gonna be use a lot of space! 

We use brute force to update the array which is not "0" row or "0" col. Otherwise, the arrays include which row and col is zero or not.

Then, we update the each row of M. If it "0" row, then we change the value 0 on entire whole value on that row.

The length of row should be "N."

And then we finally update the colums. If it is "0" colums, we change the entire values on colums as "0." 

Also, the length of column should be "M." and return. 

 

We can see it works, but it is not constant solution. This solution has O(N+M) space complexity. (Because we made two array "row" and "col."

Solution2(Constant Solution):

Constant Solution

We can see the first value "is_col_zero" which is bool variable. This is for changing all matrix[0][c] are "0" if matrix[0][0] = 0!

We use the brute force to determine which rows and cols need to be "0."

If the matrix[r][c] is "0", then we should set matrix[r][0] and matrix[0][c] as "0."

When r=0, then is_col_zero is True later.

In the second brute force, we will update the value based on whether column or row is zero or not.

If the column is zero or row is zero, then matrix[r>0][c>0] is 0. We will update matrix[r][0] and matrix[0][c] later.

 

It's time to update matirx[r][0] and matrix[0][c].

From the first brute force, we know which row is zero or not, and also which column is zero or not.