# Question

Formatted question description: https://leetcode.ca/all/73.html

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]
]

Did you use extra space?
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?

@tag-array



# Algorithm

The requirement of this question is to use O(1) space, then we cannot create a new array. We consider using the first row and first column of the original array to record whether each row and column has 0.

• Scan the first row and first column first, if there is 0, set the respective flag to true
• Then scan to remove the entire array of the first row and first column, if there is 0, assign 0 to the corresponding number in the first row and first column
• Traverse the entire array again except the first row and first column. If one of the corresponding numbers in the first row and the first column is 0, assign the current value to 0
• Finally update the first row and first column according to the flag in the first row and first column

Java