Builds on Shortest-Path BFS, which you haven’t finished yet.
0-1 BFS
You get an m x n grid where every cell carries an arrow telling you which neighbor to move to next. The arrow at grid[i][j] is one of:
1steps right, fromgrid[i][j]togrid[i][j + 1]2steps left, fromgrid[i][j]togrid[i][j - 1]3steps down, fromgrid[i][j]togrid[i + 1][j]4steps up, fromgrid[i][j]togrid[i - 1][j]
Some of these arrows may point off the edge of the grid. Starting from corner (0, 0), a valid path is any route -- no matter how long -- that reaches the opposite corner grid[m - 1][n - 1] purely by following the arrows it encounters. You may override any single cell's arrow, but each cell allows only one such override, at a cost of 1.
Return the fewest arrow overrides needed so that a route obeying the (possibly-modified) signs can reach the far corner at all.
Zero-One BFS
weighted edges (0 or 1) ➔ push 0 to front, 1 to back ➔ O(V+E) shortest path- Edge weights take many values, not just 0 and 1, as in Network Delay Time (LC 743). See Dijkstra
| 1 | from collections import deque |
| 2 | from typing import List, Tuple |
| 3 | |
| 4 | def zero_one_bfs(n: int, adj: List[List[Tuple[int, int]]], src: int) -> List[float]: |
| 5 | """0-1 BFS: shortest distance from src to every node when each edge weight is 0 or 1. |
| 6 | Time: O(V + E) | Space: O(V) |
| 7 | """ |
| 8 | dist = [float('inf')] * n |
| 9 | dist[src] = 0 |
| 10 | dq = deque([src]) |
| 11 | |
| 12 | while dq: |
| 13 | u = dq.popleft() |
| 14 | for v, weight in adj[u]: |
| 15 | if dist[u] + weight < dist[v]: # Relax: only a shorter distance re-queues v |
| 16 | dist[v] = dist[u] + weight |
| 17 | if weight == 0: |
| 18 | dq.appendleft(v) # 0-cost edge: same distance, front |
| 19 | else: |
| 20 | dq.append(v) # 1-cost edge: distance + 1, back |
| 21 | |
| 22 | return dist |
dq had when they were pushed never decrease and differ by at most 1; an entry whose node has since got a smaller dist is stale and changes nothing when popped.When every edge costs 0 or 1, the deque dq can replace Dijkstra's heap: after improving dist[v], call appendleft(v) for a 0-cost edge and append(v) for a 1-cost edge. The front then always holds the smallest distance and the deque only ever holds entries for two distances, d and d + 1 (plus stale copies of improved nodes, which change nothing when popped), so nodes leave it in the same order as from Dijkstra's heap. The trap is marking nodes visited when you add them, as in plain BFS: a node first reached by a 1-cost edge can still get a shorter distance through a 0-cost edge, so let the dist[u] + weight < dist[v] check decide.
See it run
0-1 BFS, step by step
u nonedist [0, inf, inf, inf, inf]dq [0]
The top row is dist, one column per node. The bottom row is dq from front (left) to back (right).
uthe node just popped from dqvthe neighbour whose distance is checkedpushedthe entry just added to dq
Start: dist[0] = 0 and every other node is inf. dq holds only node 0.
Gotcha 1 of 3
- The trap
Gotcha 1: Marking a node visited when it is first added
Mistakeif dist[v] == float('inf'):Fixif dist[u] + weight < dist[v]:What happens: In plain BFS, the first time a node is reached gives its distance. With 0-cost edges, that is not true. A node first reached by a 1-cost edge can later get a shorter distance through a 0-cost edge. The
dist[u] + weight < dist[v]check lets that later path win.Example: n = 3, edges 0->1 cost 1, 0->2 cost 0, 2->1 cost 0, src = 0Mistake: returns [0, 1, 0]Fix: returns [0, 0, 0]
Deep Dive
Why a deque can replace the heap
Dijkstra's algorithm always takes the node with the smallest known distance. A heap keeps the entries in that order, at a cost of O(log V) per push.
When every edge costs 0 or 1, the order can be kept more cheaply. Suppose dq is sorted by distance from front to back, and its distances differ by at most 1. Pop the front node u, with distance d. Every entry in dq has distance d or d + 1.
An edge of cost 0 gives v the distance d. That is not larger than any entry, so v goes to the front with appendleft. An edge of cost 1 gives v the distance d + 1. That is not smaller than any entry, so v goes to the back with append. In both cases dq is still sorted, and it still holds only two distances.
So the front of dq always holds the smallest distance, as the top of a heap does. Each push and pop takes O(1) time.
A trace on five nodes
Take 5 nodes and these edges, written as from -> to (cost): 0 -> 1 (1), 0 -> 2 (0), 2 -> 1 (0), 2 -> 4 (1), 1 -> 3 (1) and 3 -> 4 (0). The source is node 0.
Pop 0. The edge 0 -> 1 costs 1, so dist[1] becomes 1 and node 1 goes to the back. The edge 0 -> 2 costs 0, so dist[2] becomes 0 and node 2 goes to the front. Now dq is [2, 1].
Pop 2. The edge 2 -> 1 costs 0, and 0 + 0 < 1, so dist[1] drops from 1 to 0 and node 1 goes to the front. This is the card's trap: node 1 was first reached by a cost-1 edge, and the first distance was not the shortest. The edge 2 -> 4 costs 1, so dist[4] becomes 1. Now dq is [1, 1, 4].
The first 1 in dq is the fresh entry and the second 1 is an older copy. Pop the fresh one: the edge 1 -> 3 sets dist[3] to 1. Pop the older copy: dist[1] is already 0 and 0 + 1 < 1 is false, so nothing changes. Pop 4, which has no edges. Pop 3: 1 + 0 < 1 is false. The final dist is [0, 0, 0, 1, 1].
Stale copies and the cost
A stale entry is an older copy of a node whose dist has since become smaller. In the trace, node 1 is in dq twice. The code never removes the older copy. When it is popped, every check dist[u] + weight < dist[v] fails, because the fresh entry already did the same work.
A node can be pushed at most twice. Its first distance is some d + 1, and a later pop can lower it to d once. After that, no pop has a distance small enough to lower it again. So dq receives at most 2V entries, and the code checks each edge at most twice. The time is O(V + E) and the space is O(V).
In the trace, 5 nodes caused 6 pops and the 6 edges caused 7 edge checks. Dijkstra with a heap needs O((V + E) log V) for the same graph.
Reading a grid as a 0-1 graph
In Minimum Obstacle Removal to Reach Corner (LC 2290), a node is a cell (row, col). Moving into an empty cell costs 0. Moving into an obstacle costs 1, because you remove it. The answer is dist of the bottom-right cell.
Example: grid = [[0,1,1],[1,1,0],[1,1,0]] gives 2. The cheapest route enters two obstacle cells.
In Minimum Cost to Make at Least One Valid Path in a Grid (LC 1368), the edge that follows the arrow in the current cell costs 0, and each other direction costs 1, because you change the arrow. The same loop solves it.
The weights must be exactly 0 or 1. If an edge can cost 2 or more, the deque order breaks. Use the heap method of Network Delay Time (LC 743) instead.
60-Second Pitch
"Every edge costs 0 or 1, so I do not need a heap. I keep a deque of nodes sorted by distance. I pop the front node u. For each edge, if dist[u] + weight is smaller than dist[v], I update dist[v]. A cost-0 edge puts v at the front, and a cost-1 edge puts it at the back, so the deque stays sorted and holds only two distances. I must not mark a node as visited when I first add it, because a later cost-0 edge can give a shorter distance. The < check decides. A node can be pushed at most twice, so the time is O(V + E) and the space is O(V)."
Common Questions
- Why is this faster than Dijkstra, and is it still correct?
Dijkstra needs a heap to find the smallest distance, which costs O(log V) per operation. With weights 0 and 1, the deque stays sorted by distance with only
O(1)operations, so the front is always the smallest distance. The pop order is the same as the heap's, so the correctness argument of Dijkstra still applies. The time isO(V + E)instead of O((V + E) log V).- Can the same node be in
dqmore than once? Yes, at most twice. The first entry has distance
d + 1, and a later cost-0 edge can lower it todand push a second entry to the front. The older entry is stale. When it is popped, everydist[u] + weight < dist[v]check fails, so it changes nothing.- What if the graph has a cycle of cost-0 edges?
The loop still ends. A node is pushed only when its distance gets strictly smaller, and a cost-0 cycle cannot make a distance smaller. With
<=it would loop forever, which is why the card uses<.- What do you do if weights can be 0, 1 or 2?
The deque no longer keeps only two distances, so it is not sorted. Use a heap, as in Network Delay Time (LC 743), which costs O((V + E) log V). A bucket queue with one list per distance also works when the maximum weight is small.
- How do you model a grid problem such as Minimum Obstacle Removal to Reach Corner (LC 2290)?
Each cell is a node with up to four neighbours. The cost of an edge is the cost to enter the next cell: 0 for an empty cell and 1 for an obstacle. Run the card's loop from the top-left cell and read
distof the bottom-right cell. No explicit edge list is needed, because the neighbours come from the grid.
SWE Reasoning
Spot it
- Every move either costs nothing or costs exactly 1: follow an arrow or change it, walk through an empty cell or remove an obstacle, stay in a lane or switch lanes.
- The question asks for the smallest total cost, not the smallest number of moves. Plain BFS counts moves, so it gives the wrong answer here.
- You started to write Dijkstra, and you noticed that the only weights are 0 and 1.
- The answer is a distance to one target cell, or to every node, with
O(V + E)time as the goal.
The invariant, step by step
dist[src] = 0, every other distance isfloat('inf'), anddqholds onlysrc.u = dq.popleft()takes the front entry. The front holds the smallest distance, and every entry indqhas distancedord + 1for the front distanced.- For each edge
(v, weight), the checkdist[u] + weight < dist[v]asks whether this route is shorter than every route found so far. - If it is,
dist[v]is lowered. A cost-0 edge putsvat the front, with distanced. A cost-1 edge putsvat the back, with distanced + 1. - In both cases
dqstays sorted, so the next pop again has the smallest distance. - If
valready had an entry indq, that older entry is now stale. When it is popped, all its checks fail and nothing changes. - When
dqis empty, no route can lower any distance, sodistholds the shortest distances.
Traps
- Visited on first push.
if dist[v] == float('inf'):fixes a distance the first time a node is reached. A node first reached by a cost-1 edge can get a shorter distance through a cost-0 edge. In the trace, node 1 would stay at 1 and the answer would be[0, 1, 0, 2, 1], not[0, 0, 0, 1, 1]. <=instead of<. An equal distance would pushvagain. On a cycle of cost-0 edges, nodes push each other forever and the loop never ends.- Swapped
appendleftandappend. Nodes leavedqbefore their distance is final. The checks can still repair the answer, but nodes are processed again and the run is no longerO(V + E). - A weight that is not 0 or 1. The two-distance property fails, so
dqis no longer sorted. Use a heap. - Treating stale entries as an error. Do not try to delete them. Popping one is harmless, and the checks make it free of effect.
Practice
Builds on Shortest-Path BFS, which you haven’t finished yet.
0-1 BFS
You get an m x n grid where every cell carries an arrow telling you which neighbor to move to next. The arrow at grid[i][j] is one of:
1steps right, fromgrid[i][j]togrid[i][j + 1]2steps left, fromgrid[i][j]togrid[i][j - 1]3steps down, fromgrid[i][j]togrid[i + 1][j]4steps up, fromgrid[i][j]togrid[i - 1][j]
Some of these arrows may point off the edge of the grid. Starting from corner (0, 0), a valid path is any route -- no matter how long -- that reaches the opposite corner grid[m - 1][n - 1] purely by following the arrows it encounters. You may override any single cell's arrow, but each cell allows only one such override, at a cost of 1.
Return the fewest arrow overrides needed so that a route obeying the (possibly-modified) signs can reach the far corner at all.
Zero-One BFS
weighted edges (0 or 1) ➔ push 0 to front, 1 to back ➔ O(V+E) shortest path- Edge weights take many values, not just 0 and 1, as in Network Delay Time (LC 743). See Dijkstra
| 1 | from collections import deque |
| 2 | from typing import List, Tuple |
| 3 | |
| 4 | def zero_one_bfs(n: int, adj: List[List[Tuple[int, int]]], src: int) -> List[float]: |
| 5 | """0-1 BFS: shortest distance from src to every node when each edge weight is 0 or 1. |
| 6 | Time: O(V + E) | Space: O(V) |
| 7 | """ |
| 8 | dist = [float('inf')] * n |
| 9 | dist[src] = 0 |
| 10 | dq = deque([src]) |
| 11 | |
| 12 | while dq: |
| 13 | u = dq.popleft() |
| 14 | for v, weight in adj[u]: |
| 15 | if dist[u] + weight < dist[v]: # Relax: only a shorter distance re-queues v |
| 16 | dist[v] = dist[u] + weight |
| 17 | if weight == 0: |
| 18 | dq.appendleft(v) # 0-cost edge: same distance, front |
| 19 | else: |
| 20 | dq.append(v) # 1-cost edge: distance + 1, back |
| 21 | |
| 22 | return dist |
dq had when they were pushed never decrease and differ by at most 1; an entry whose node has since got a smaller dist is stale and changes nothing when popped.When every edge costs 0 or 1, the deque dq can replace Dijkstra's heap: after improving dist[v], call appendleft(v) for a 0-cost edge and append(v) for a 1-cost edge. The front then always holds the smallest distance and the deque only ever holds entries for two distances, d and d + 1 (plus stale copies of improved nodes, which change nothing when popped), so nodes leave it in the same order as from Dijkstra's heap. The trap is marking nodes visited when you add them, as in plain BFS: a node first reached by a 1-cost edge can still get a shorter distance through a 0-cost edge, so let the dist[u] + weight < dist[v] check decide.
See it run
0-1 BFS, step by step
u nonedist [0, inf, inf, inf, inf]dq [0]
The top row is dist, one column per node. The bottom row is dq from front (left) to back (right).
uthe node just popped from dqvthe neighbour whose distance is checkedpushedthe entry just added to dq
Start: dist[0] = 0 and every other node is inf. dq holds only node 0.
Gotcha 1 of 3
- The trap
Gotcha 1: Marking a node visited when it is first added
Mistakeif dist[v] == float('inf'):Fixif dist[u] + weight < dist[v]:What happens: In plain BFS, the first time a node is reached gives its distance. With 0-cost edges, that is not true. A node first reached by a 1-cost edge can later get a shorter distance through a 0-cost edge. The
dist[u] + weight < dist[v]check lets that later path win.Example: n = 3, edges 0->1 cost 1, 0->2 cost 0, 2->1 cost 0, src = 0Mistake: returns [0, 1, 0]Fix: returns [0, 0, 0]
Deep Dive
Why a deque can replace the heap
Dijkstra's algorithm always takes the node with the smallest known distance. A heap keeps the entries in that order, at a cost of O(log V) per push.
When every edge costs 0 or 1, the order can be kept more cheaply. Suppose dq is sorted by distance from front to back, and its distances differ by at most 1. Pop the front node u, with distance d. Every entry in dq has distance d or d + 1.
An edge of cost 0 gives v the distance d. That is not larger than any entry, so v goes to the front with appendleft. An edge of cost 1 gives v the distance d + 1. That is not smaller than any entry, so v goes to the back with append. In both cases dq is still sorted, and it still holds only two distances.
So the front of dq always holds the smallest distance, as the top of a heap does. Each push and pop takes O(1) time.
A trace on five nodes
Take 5 nodes and these edges, written as from -> to (cost): 0 -> 1 (1), 0 -> 2 (0), 2 -> 1 (0), 2 -> 4 (1), 1 -> 3 (1) and 3 -> 4 (0). The source is node 0.
Pop 0. The edge 0 -> 1 costs 1, so dist[1] becomes 1 and node 1 goes to the back. The edge 0 -> 2 costs 0, so dist[2] becomes 0 and node 2 goes to the front. Now dq is [2, 1].
Pop 2. The edge 2 -> 1 costs 0, and 0 + 0 < 1, so dist[1] drops from 1 to 0 and node 1 goes to the front. This is the card's trap: node 1 was first reached by a cost-1 edge, and the first distance was not the shortest. The edge 2 -> 4 costs 1, so dist[4] becomes 1. Now dq is [1, 1, 4].
The first 1 in dq is the fresh entry and the second 1 is an older copy. Pop the fresh one: the edge 1 -> 3 sets dist[3] to 1. Pop the older copy: dist[1] is already 0 and 0 + 1 < 1 is false, so nothing changes. Pop 4, which has no edges. Pop 3: 1 + 0 < 1 is false. The final dist is [0, 0, 0, 1, 1].
Stale copies and the cost
A stale entry is an older copy of a node whose dist has since become smaller. In the trace, node 1 is in dq twice. The code never removes the older copy. When it is popped, every check dist[u] + weight < dist[v] fails, because the fresh entry already did the same work.
A node can be pushed at most twice. Its first distance is some d + 1, and a later pop can lower it to d once. After that, no pop has a distance small enough to lower it again. So dq receives at most 2V entries, and the code checks each edge at most twice. The time is O(V + E) and the space is O(V).
In the trace, 5 nodes caused 6 pops and the 6 edges caused 7 edge checks. Dijkstra with a heap needs O((V + E) log V) for the same graph.
Reading a grid as a 0-1 graph
In Minimum Obstacle Removal to Reach Corner (LC 2290), a node is a cell (row, col). Moving into an empty cell costs 0. Moving into an obstacle costs 1, because you remove it. The answer is dist of the bottom-right cell.
Example: grid = [[0,1,1],[1,1,0],[1,1,0]] gives 2. The cheapest route enters two obstacle cells.
In Minimum Cost to Make at Least One Valid Path in a Grid (LC 1368), the edge that follows the arrow in the current cell costs 0, and each other direction costs 1, because you change the arrow. The same loop solves it.
The weights must be exactly 0 or 1. If an edge can cost 2 or more, the deque order breaks. Use the heap method of Network Delay Time (LC 743) instead.
60-Second Pitch
"Every edge costs 0 or 1, so I do not need a heap. I keep a deque of nodes sorted by distance. I pop the front node u. For each edge, if dist[u] + weight is smaller than dist[v], I update dist[v]. A cost-0 edge puts v at the front, and a cost-1 edge puts it at the back, so the deque stays sorted and holds only two distances. I must not mark a node as visited when I first add it, because a later cost-0 edge can give a shorter distance. The < check decides. A node can be pushed at most twice, so the time is O(V + E) and the space is O(V)."
Common Questions
- Why is this faster than Dijkstra, and is it still correct?
Dijkstra needs a heap to find the smallest distance, which costs O(log V) per operation. With weights 0 and 1, the deque stays sorted by distance with only
O(1)operations, so the front is always the smallest distance. The pop order is the same as the heap's, so the correctness argument of Dijkstra still applies. The time isO(V + E)instead of O((V + E) log V).- Can the same node be in
dqmore than once? Yes, at most twice. The first entry has distance
d + 1, and a later cost-0 edge can lower it todand push a second entry to the front. The older entry is stale. When it is popped, everydist[u] + weight < dist[v]check fails, so it changes nothing.- What if the graph has a cycle of cost-0 edges?
The loop still ends. A node is pushed only when its distance gets strictly smaller, and a cost-0 cycle cannot make a distance smaller. With
<=it would loop forever, which is why the card uses<.- What do you do if weights can be 0, 1 or 2?
The deque no longer keeps only two distances, so it is not sorted. Use a heap, as in Network Delay Time (LC 743), which costs O((V + E) log V). A bucket queue with one list per distance also works when the maximum weight is small.
- How do you model a grid problem such as Minimum Obstacle Removal to Reach Corner (LC 2290)?
Each cell is a node with up to four neighbours. The cost of an edge is the cost to enter the next cell: 0 for an empty cell and 1 for an obstacle. Run the card's loop from the top-left cell and read
distof the bottom-right cell. No explicit edge list is needed, because the neighbours come from the grid.
SWE Reasoning
Spot it
- Every move either costs nothing or costs exactly 1: follow an arrow or change it, walk through an empty cell or remove an obstacle, stay in a lane or switch lanes.
- The question asks for the smallest total cost, not the smallest number of moves. Plain BFS counts moves, so it gives the wrong answer here.
- You started to write Dijkstra, and you noticed that the only weights are 0 and 1.
- The answer is a distance to one target cell, or to every node, with
O(V + E)time as the goal.
The invariant, step by step
dist[src] = 0, every other distance isfloat('inf'), anddqholds onlysrc.u = dq.popleft()takes the front entry. The front holds the smallest distance, and every entry indqhas distancedord + 1for the front distanced.- For each edge
(v, weight), the checkdist[u] + weight < dist[v]asks whether this route is shorter than every route found so far. - If it is,
dist[v]is lowered. A cost-0 edge putsvat the front, with distanced. A cost-1 edge putsvat the back, with distanced + 1. - In both cases
dqstays sorted, so the next pop again has the smallest distance. - If
valready had an entry indq, that older entry is now stale. When it is popped, all its checks fail and nothing changes. - When
dqis empty, no route can lower any distance, sodistholds the shortest distances.
Traps
- Visited on first push.
if dist[v] == float('inf'):fixes a distance the first time a node is reached. A node first reached by a cost-1 edge can get a shorter distance through a cost-0 edge. In the trace, node 1 would stay at 1 and the answer would be[0, 1, 0, 2, 1], not[0, 0, 0, 1, 1]. <=instead of<. An equal distance would pushvagain. On a cycle of cost-0 edges, nodes push each other forever and the loop never ends.- Swapped
appendleftandappend. Nodes leavedqbefore their distance is final. The checks can still repair the answer, but nodes are processed again and the run is no longerO(V + E). - A weight that is not 0 or 1. The two-distance property fails, so
dqis no longer sorted. Use a heap. - Treating stale entries as an error. Do not try to delete them. Popping one is harmless, and the checks make it free of effect.