Where it runs
1. The problem
You have a grid of numbers. The rule is simple: if a cell holds 0, its whole row and its whole column must become 0 too. One zero turns a whole cross of cells into zeros.
The hard part is the phrase "in place". You may not build a new copy of the grid for the answer. You must change the grid you were given, and spend almost no extra memory.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- does the word exist as a path on the board
- trace letters through adjacent cells, no reuse
- DFS with backtracking on a grid
- mark a cell as visited, then undo it
Looks similar, isn't
- Backtracking
This is backtracking with the grid as the tree. The choices are the four neighbours.
- Graph BFS / DFS
A traversal marks a cell once and forever. Here the mark comes off on the way out.
- Connected components
Flood fill also walks neighbours, but it never unmarks. It is counting rather than searching.
- Trie (prefix tree)
With many words to find, a trie prunes the walk. Without one each word costs its own search.
An r by c grid with a word of length L costs O(rc times 4L). Pruning is what makes it run.
On LeetCode
Matrix problems where a cell changes its whole row or column, or where each new value depends on the old grid. Record the marks first and apply them in a second pass, and use row 0 and column 0 as the notepad when the space must be O(1).
The lesson task, word for word.
Count the 1s in each row and each column first, and a 1 is special when both its counts are 1.
Count the ones per row and per column in one pass, then fill each cell from its two counts in a second pass.
Every cell changes based on the old grid, so mark the change in place with two extra values, such as 2 for dies and 3 for is born, and decode them in a second pass.