Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Use the first row and column as markers: The Zero Cross.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Set matrix zeroes matches the clues
- 2Keep this true after every move: marker cells record every interior row and column that must become zero
- 3Reach the result within O(rows times cols) time and O(1) extra space
Rules and pressure
- Target cost: O(rows times cols) time and O(1) extra space
- State rule: marker cells record every interior row and column that must become zero
Lesson 1 of 3
Live algorithm trace
Set matrix zeroes
Complete execution1 of 5
Record whether the marker row or column already needs clearing.
1
remember whether first row or column contains zero2
scan interior zeros3
mark their first-row column and first-column row4
zero marked interior cells5
zero first row and column if remembered6
return matrixfirstRowZero = falsefirstColZero = false
Truth to preserve / Cost target
Truth to preserve
marker cells record every interior row and column that must become zero
Cost target
O(rows times cols) time and O(1) extra space
A zero erases its full row and column. Store row and column markers in the matrix's first row and column, while remembering their original zero states separately.
Your call · What should guide every step of this algorithm?