237. Zero Spread
A factory's quality sheet is a grid of sensor readings. A reading of 0 means a sensor has failed, and a failed sensor makes every other reading in its row and in its column untrustworthy. Rewrite the sheet in place: for every cell that holds 0 in the original sheet, set the entire row and the entire column of that cell to 0.
Be careful: zeros that you create during the rewrite must not spread further; only the zeros present at the start count. The function changes grid and returns nothing. A solution that copies the whole sheet works, but the intended challenge is to use only constant extra memory by storing the markers inside the sheet itself.
Example 1
- Input:
- grid = [[4,7,2],[5,0,9],[6,8,3]]
- Output:
- [[4,0,2],[0,0,0],[6,0,3]]
- Explanation:
The only zero is at row 1, column 1, so row 1 and column 1 become all zero: [[4,0,2],[0,0,0],[6,0,3]].
Example 2
- Input:
- grid = [[1,2],[3,4]]
- Output:
- [[1,2],[3,4]]
- Explanation:
There are no zeros, so nothing changes.
Example 3
- Input:
- grid = [[0,5,6],[7,8,9],[1,2,0]]
- Output:
- [[0,0,0],[0,8,0],[0,0,0]]
- Explanation:
Zeros at (0,0) and (2,2) clear rows 0 and 2 and columns 0 and 2. Only the centre cell 8 survives, and the new zeros do not create further clearing.
Constraints
1 ≤ rows, columns ≤ 1000
-109 ≤ grid[i][j] ≤ 109
The function modifies grid and returns nothing.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Graded
- Your answer is read from
gridafter your method returns. - Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(m × n)
- Space
- O(1)