Blank Out Rows and Columns
MediumMatrix
Problem
A seating plan is an m × n grid where each cell holds a ticket number, and 0 marks a broken seat. Safety rules say that if a seat is broken, its entire row and entire column must be closed.
Modify grid in place so that every row and every column containing an original 0 is filled with zeros. Try to use only O(1) extra memory. The function returns nothing.
Example 1
- Input:
- grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
- Output:
- [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
The single 0 closes row 1 and column 1.
Example 2
- Input:
- grid = [[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]]
Constraints
- 1 ≤ m, n ≤ 200
- -2^31 ≤ grid[i][j] ≤ 2^31 - 1
Hint
Show the first hint
Zeroing as you scan is a trap: new zeros would trigger more zeroing. First record which rows and columns to clear.
Walkthrough
How to approach it
01Clarify before coding
- Only original zeros trigger clearing? Yes, zeros you write must not spread further.
- Return a new grid or mutate? Mutate in place and return nothing.
- Is O(m + n) memory acceptable? It is a valid first answer; the target is O(1).
02Brute force
Copy the grid, scan the copy for zeros and clear rows and columns in the original; or keep two sets of rows and columns to clear.
Cost: The copy costs O(m · n) memory; the two sets cost O(m + n). Both are O(m · n) time.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.