Minimum Cost to Make at Least One Valid Path in a Grid (LeetCode 1368)
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.
Worked Examples
grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]3grid = [[1,1,3],[3,2,2],[1,1,4]]0grid = [[1,2],[4,3]]1(0,0) the arrow leads right to (0,1), whose arrow points back left. Changing that one arrow to point down reaches the goal, for a cost of 1.⚖️Formal Constraints & Bounds
m == grid.lengthn == grid[i].length1 <= m, n <= 1001 <= grid[i][j] <= 4
Core Insight
Pushing 0-cost neighbors (cells reached by following the existing arrow) to the front and 1-cost neighbors (cells reached by overriding it) to the back keeps the deque sorted by distance at all times, without ever needing a heap.
Real-World Scenario & Production Applications
Autonomous-routing systems (warehouse robots, road-network signage) where following the existing directional signage is free, but overriding a sign to force a different route costs a fixed unit of resource — exactly the 0/1 edge-weight shape 0-1 BFS is built for.
Subproblems & Recurrence Decomposition3 Phases
Start a double-ended queue holding (row, col, cost) from the upper-left cell (0, 0) with cost 0, plus an empty visited set — no distance table needed since the deque itself stays sorted by cost.
queue = deque([(0, 0, 0)]) # (r, c, cost)
visited = set()Step-by-Step Execution Trace Table
Step-by-Step Wavefront Progression (Example 3, grid = [[1,2],[4,3]])
| Step | Queue Action | Popped Cell (r, c) | dist[r][c] | Moves Tried (right, left, down, up) | dist After | Resulting dq (Front → Back) |
|---|---|---|---|---|---|---|
| 0 | Seed | — | — | dist[0][0] = 0 | [[0, inf], [inf, inf]] | [(0, 0)] |
| 1 | popleft() | (0, 0), arrow 1 (right) | 0 | Right -> (0, 1): weight 0, 0 < inf, appendleftDown -> (1, 0): weight 1, 1 < inf, append | [[0, 0], [1, inf]] | [(0, 1), (1, 0)] |
| 2 | popleft() | (0, 1), arrow 2 (left) | 0 | Left -> (0, 0): weight 0, 0 < 0 is falseDown -> (1, 1): weight 1, 1 < inf, append | [[0, 0], [1, 1]] | [(1, 0), (1, 1)] |
| 3 | popleft() | (1, 0), arrow 4 (up) | 1 | Right -> (1, 1): weight 1, 2 < 1 is falseUp -> (0, 0): weight 0, 1 < 0 is false | unchanged | [(1, 1)] |
| 4 | popleft() | (1, 1), arrow 3 (down) | 1 | Left -> (1, 0): weight 1, 2 < 1 is falseUp -> (0, 1): weight 1, 2 < 0 is false | unchanged | [] |
| 5 | Loop ends | — | — | — | — | Return dist[1][1] = 1 ✅ |
grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]3Step-by-Step Wavefront Progression (Example 3, grid = [[1,2],[4,3]])
| Step | Queue Action | Popped Cell (r, c) | dist[r][c] | Moves Tried (right, left, down, up) | dist After | Resulting dq (Front → Back) |
|---|---|---|---|---|---|---|
| 0 | Seed | — | — | dist[0][0] = 0 | [[0, inf], [inf, inf]] | [(0, 0)] |
| 1 | popleft() | (0, 0), arrow 1 (right) | 0 | Right -> (0, 1): weight 0, 0 < inf, appendleftDown -> (1, 0): weight 1, 1 < inf, append | [[0, 0], [1, inf]] | [(0, 1), (1, 0)] |
| 2 | popleft() | (0, 1), arrow 2 (left) | 0 | Left -> (0, 0): weight 0, 0 < 0 is falseDown -> (1, 1): weight 1, 1 < inf, append | [[0, 0], [1, 1]] | [(1, 0), (1, 1)] |
| 3 | popleft() | (1, 0), arrow 4 (up) | 1 | Right -> (1, 1): weight 1, 2 < 1 is falseUp -> (0, 0): weight 0, 1 < 0 is false | unchanged | [(1, 1)] |
| 4 | popleft() | (1, 1), arrow 3 (down) | 1 | Left -> (1, 0): weight 1, 2 < 1 is falseUp -> (0, 1): weight 1, 2 < 0 is false | unchanged | [] |
| 5 | Loop ends | — | — | — | — | Return dist[1][1] = 1 ✅ |
| 1 | moves = [(0, 1), (0, -1), (1, 0), (-1, 0)] |
| 2 | dist = [[inf] * n for _ in range(m)] |
| 3 | dist[0][0] = 0 |
| 4 | dq = deque([(0, 0)]) |
| 5 | while dq: |
| 6 | r, c = dq.popleft() |
| 7 | for sign, (dr, dc) in enumerate(moves, start=1): |
| 8 | nr, nc = r + dr, c + dc |
| 9 | skip (nr, nc) if it is outside the grid |
| 10 | weight = 0 if grid[r][c] == sign else 1 |
| 11 | if dist[r][c] + weight < dist[nr][nc]: |
| 12 | dist[nr][nc] = dist[r][c] + weight |
| 13 | appendleft((nr, nc)) when weight is 0, else append((nr, nc)) |
| 14 | return dist[m - 1][n - 1] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
When edge weights in a graph are restricted strictly to and , Dijkstra's priority queue overhead is unnecessary. A Double-Ended Queue (Deque) maintains the frontier: transitions with weight push to the front of the deque, while transitions with weight push to the back. This preserves a 2-level monotonic wavefront, solving shortest path in strict linear time.
🚇 The Analogy: A Train Line With Free Transfers
Imagine a transit system where every ride costs one fare, except transferring between two trains stopped at the same platform — that's free. If you're tracking "how many fares have I spent so far," a free transfer doesn't move you to a new fare-tier at all — you're still exactly where you were, just now sitting on a different train. A paid ride, on the other hand, always bumps you into the next fare-tier. So free transfers should be explored immediately, before any paid ride, because they haven't cost you anything yet — you're not skipping ahead, you're just finishing exploring your current tier.
🔑 The Key Idea in the Code
This is why a deque works and a plain queue doesn't: at any moment, the deque holds a mix of "current tier" and "next tier" nodes, and pushing 0-cost neighbors to the front guarantees they get explored before the current tier is considered finished — preserving the same "process closest things first" guarantee plain BFS relies on, without needing a full priority queue.
There's one subtlety worth calling out: a station can get pushed onto the deque twice — once via an expensive route, and again when a cheaper route to it turns up before the first copy is processed. So never mark a stop as done the moment it's pushed, the way plain BFS does — that would lock in the expensive route. Instead, push again whenever dist[u] + weight < dist[v]; the older copy is stale and changes nothing when it's popped later.
Swapping the two pushes: A 0-cost move goes to the front with
appendleftand a 1-cost move to the back withappend. Swapped, cells leave the deque out of distance order and are relaxed again and again, losing the linear bound. (A heap-based Dijkstra is not a pitfall: it gives the same answer, only with an extra log factor.)Marking visited on enqueue in 0-1 BFS: In unweighted BFS, marking visited on push is standard. In 0-1 BFS, a cell might be enqueued with cost 1 and later reached with cost 0. Cells must only be finalized when popped, or updated whenever
new_cost < dist[nr][nc].1-based grid arrow encoding mismatch: Arrows are 1-indexed: 1 = Right, 2 = Left, 3 = Down, 4 = Up. Forgetting the offset when comparing
grid[r][c] == direction_indexcalculates incorrect edge costs.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Every cell's arrow tells you which neighbour to move to, following it is free, and you may "override" an arrow "at a cost of 1"; the question is the "fewest arrow overrides" to reach the far corner. That is a shortest path where each move costs 0 (follow the arrow) or 1 (change it): the need Zero-One BFS serves.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Read front to back, the distances the entries of dq had when they were pushed never decrease and differ by at most 1; an entry whose cell has since got a smaller dist is stale and changes nothing when popped. The decision: move to (nr, nc) only when dist[r][c] + weight < dist[nr][nc], where weight = 0 if grid[r][c] == sign else 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
No visited-on-enqueue set, as in plain BFS: a cell first reached by a 1-cost move can still get a smaller
distthrough a 0-cost move, so letdist[r][c] + weight < dist[nr][nc]decide.weight = 0 if grid[r][c] == sign else 1: the weight comes from the arrow of the cell you leave,grid[r][c], not the cell you enter, and signs are 1-4 in the order right, left, down, up (enumerate(moves, start=1)).dq.appendleftfor weight 0 anddq.appendfor weight 1: swapped, cells leave out of distance order and are pushed again and again (the finaldistis still right, but the linear bound is gone, and an early return at the corner would give a wrong answer), with no error.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Zero-One BFS. Each cell is a node, and a move to a neighbour costs zero if the cell's arrow already points there and one if I have to change the arrow. With only two weights I don't need Dijkstra's heap: I keep dist per cell and a deque. When a move gives a neighbour a smaller distance, I update it and push it to the front for a zero-cost move, or to the back for a one-cost move. So the deque always holds entries for just two distances, d at the front and d plus one behind them, and cells leave in the same order a heap would give. The trap is marking cells visited when I push them, like plain BFS: a cell first reached by a paid move can still get cheaper through a free one, so only the distance check decides. It's O(M times N) time and space, since each cell has at most four moves.
Complexity & Mathematical Proof
O(V + E)
Look at the code: a cell is pushed only when dist[r][c] + weight < dist[nr][nc] lowers its dist, and with 0/1 weights that happens at most twice per cell (first to d + 1, then at most once more to d), so while dq pops at most 2V entries. Each pop runs for sign, (dr, dc) in enumerate(moves, start=1) over 4 moves with O(1) work (bounds test, weight, one comparison, at most one push), and E ≤ 4V. Total: O(V + E) = O(M · N).
O(V)
dist holds one entry per cell, O(V), and dq holds at most two entries per cell, O(V). No recursion: the call stack is O(1). The input grid is not counted, and the answer is one integer.
T(V) ≤ 2V pops · 4 moves = 8V = O(V + E), V = M · N
Derivation Progression
if dist[r][c] + weight < dist[nr][nc]: ... ≤ 2 pushes per cell
Pops come out in non-decreasing distance order, so a cell's dist can drop at most twice (to d + 1, then to d): at most 2V pushes and 2V pops.
for sign, (dr, dc) in enumerate(moves, start=1): 4 moves
Each move is a bounds test, weight = 0 if grid[r][c] == sign else 1, one comparison and at most one appendleft or append, all O(1).
≤ 2V · 4 = 8V = O(V + E)
Multiplying the two bounds gives O(V + E) = O(M · N): the deque pops in O(1) where a heap would pay O(log V).
Variable Definitions
Number of rows in the grid
Number of columns in the grid
Number of cells, M · N
Number of moves between neighbouring cells, at most 4 · V
Memory Architecture & Bounds
O(1) (no recursion)
O(V): dist (V entries) and dq (at most 2V entries)
O(1): one integer
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "override" an arrow "at a cost of 1", following it is free, "fewest arrow overrides". A shortest path whose moves cost only 0 or 1: Zero-One BFS. At scale the same two-weight shape shows up wherever most steps are free and a few are charged, and it is worth spotting because the deque keeps the frontier in order without a heap.
cells and moves: at most pops of 4 moves each, about checks. dist is numbers; on a map with cells it would be the first thing to run out of memory, not the deque.
More than two weights (for example 0, 1 and 2) break the two-distance deque: that needs a bucket per distance (Dial's algorithm) or Dijkstra.
Core Algorithmic State Invariants
- The Answer Is Read After the Loop
The loop runs until dq is empty and then returns dist[m - 1][n - 1]. Every cell is reachable once arrows may change, so the corner always gets a finite distance; no -1 case exists in this problem.
Minimum Cost to Make at Least One Valid Path in a Grid (LeetCode 1368)
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.
Worked Examples
grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]3grid = [[1,1,3],[3,2,2],[1,1,4]]0grid = [[1,2],[4,3]]1(0,0) the arrow leads right to (0,1), whose arrow points back left. Changing that one arrow to point down reaches the goal, for a cost of 1.⚖️Formal Constraints & Bounds
m == grid.lengthn == grid[i].length1 <= m, n <= 1001 <= grid[i][j] <= 4
Core Insight
Pushing 0-cost neighbors (cells reached by following the existing arrow) to the front and 1-cost neighbors (cells reached by overriding it) to the back keeps the deque sorted by distance at all times, without ever needing a heap.
Real-World Scenario & Production Applications
Autonomous-routing systems (warehouse robots, road-network signage) where following the existing directional signage is free, but overriding a sign to force a different route costs a fixed unit of resource — exactly the 0/1 edge-weight shape 0-1 BFS is built for.
Subproblems & Recurrence Decomposition3 Phases
Start a double-ended queue holding (row, col, cost) from the upper-left cell (0, 0) with cost 0, plus an empty visited set — no distance table needed since the deque itself stays sorted by cost.
queue = deque([(0, 0, 0)]) # (r, c, cost)
visited = set()Step-by-Step Execution Trace Table
Step-by-Step Wavefront Progression (Example 3, grid = [[1,2],[4,3]])
| Step | Queue Action | Popped Cell (r, c) | dist[r][c] | Moves Tried (right, left, down, up) | dist After | Resulting dq (Front → Back) |
|---|---|---|---|---|---|---|
| 0 | Seed | — | — | dist[0][0] = 0 | [[0, inf], [inf, inf]] | [(0, 0)] |
| 1 | popleft() | (0, 0), arrow 1 (right) | 0 | Right -> (0, 1): weight 0, 0 < inf, appendleftDown -> (1, 0): weight 1, 1 < inf, append | [[0, 0], [1, inf]] | [(0, 1), (1, 0)] |
| 2 | popleft() | (0, 1), arrow 2 (left) | 0 | Left -> (0, 0): weight 0, 0 < 0 is falseDown -> (1, 1): weight 1, 1 < inf, append | [[0, 0], [1, 1]] | [(1, 0), (1, 1)] |
| 3 | popleft() | (1, 0), arrow 4 (up) | 1 | Right -> (1, 1): weight 1, 2 < 1 is falseUp -> (0, 0): weight 0, 1 < 0 is false | unchanged | [(1, 1)] |
| 4 | popleft() | (1, 1), arrow 3 (down) | 1 | Left -> (1, 0): weight 1, 2 < 1 is falseUp -> (0, 1): weight 1, 2 < 0 is false | unchanged | [] |
| 5 | Loop ends | — | — | — | — | Return dist[1][1] = 1 ✅ |
grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]3Step-by-Step Wavefront Progression (Example 3, grid = [[1,2],[4,3]])
| Step | Queue Action | Popped Cell (r, c) | dist[r][c] | Moves Tried (right, left, down, up) | dist After | Resulting dq (Front → Back) |
|---|---|---|---|---|---|---|
| 0 | Seed | — | — | dist[0][0] = 0 | [[0, inf], [inf, inf]] | [(0, 0)] |
| 1 | popleft() | (0, 0), arrow 1 (right) | 0 | Right -> (0, 1): weight 0, 0 < inf, appendleftDown -> (1, 0): weight 1, 1 < inf, append | [[0, 0], [1, inf]] | [(0, 1), (1, 0)] |
| 2 | popleft() | (0, 1), arrow 2 (left) | 0 | Left -> (0, 0): weight 0, 0 < 0 is falseDown -> (1, 1): weight 1, 1 < inf, append | [[0, 0], [1, 1]] | [(1, 0), (1, 1)] |
| 3 | popleft() | (1, 0), arrow 4 (up) | 1 | Right -> (1, 1): weight 1, 2 < 1 is falseUp -> (0, 0): weight 0, 1 < 0 is false | unchanged | [(1, 1)] |
| 4 | popleft() | (1, 1), arrow 3 (down) | 1 | Left -> (1, 0): weight 1, 2 < 1 is falseUp -> (0, 1): weight 1, 2 < 0 is false | unchanged | [] |
| 5 | Loop ends | — | — | — | — | Return dist[1][1] = 1 ✅ |
| 1 | moves = [(0, 1), (0, -1), (1, 0), (-1, 0)] |
| 2 | dist = [[inf] * n for _ in range(m)] |
| 3 | dist[0][0] = 0 |
| 4 | dq = deque([(0, 0)]) |
| 5 | while dq: |
| 6 | r, c = dq.popleft() |
| 7 | for sign, (dr, dc) in enumerate(moves, start=1): |
| 8 | nr, nc = r + dr, c + dc |
| 9 | skip (nr, nc) if it is outside the grid |
| 10 | weight = 0 if grid[r][c] == sign else 1 |
| 11 | if dist[r][c] + weight < dist[nr][nc]: |
| 12 | dist[nr][nc] = dist[r][c] + weight |
| 13 | appendleft((nr, nc)) when weight is 0, else append((nr, nc)) |
| 14 | return dist[m - 1][n - 1] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
When edge weights in a graph are restricted strictly to and , Dijkstra's priority queue overhead is unnecessary. A Double-Ended Queue (Deque) maintains the frontier: transitions with weight push to the front of the deque, while transitions with weight push to the back. This preserves a 2-level monotonic wavefront, solving shortest path in strict linear time.
🚇 The Analogy: A Train Line With Free Transfers
Imagine a transit system where every ride costs one fare, except transferring between two trains stopped at the same platform — that's free. If you're tracking "how many fares have I spent so far," a free transfer doesn't move you to a new fare-tier at all — you're still exactly where you were, just now sitting on a different train. A paid ride, on the other hand, always bumps you into the next fare-tier. So free transfers should be explored immediately, before any paid ride, because they haven't cost you anything yet — you're not skipping ahead, you're just finishing exploring your current tier.
🔑 The Key Idea in the Code
This is why a deque works and a plain queue doesn't: at any moment, the deque holds a mix of "current tier" and "next tier" nodes, and pushing 0-cost neighbors to the front guarantees they get explored before the current tier is considered finished — preserving the same "process closest things first" guarantee plain BFS relies on, without needing a full priority queue.
There's one subtlety worth calling out: a station can get pushed onto the deque twice — once via an expensive route, and again when a cheaper route to it turns up before the first copy is processed. So never mark a stop as done the moment it's pushed, the way plain BFS does — that would lock in the expensive route. Instead, push again whenever dist[u] + weight < dist[v]; the older copy is stale and changes nothing when it's popped later.
Swapping the two pushes: A 0-cost move goes to the front with
appendleftand a 1-cost move to the back withappend. Swapped, cells leave the deque out of distance order and are relaxed again and again, losing the linear bound. (A heap-based Dijkstra is not a pitfall: it gives the same answer, only with an extra log factor.)Marking visited on enqueue in 0-1 BFS: In unweighted BFS, marking visited on push is standard. In 0-1 BFS, a cell might be enqueued with cost 1 and later reached with cost 0. Cells must only be finalized when popped, or updated whenever
new_cost < dist[nr][nc].1-based grid arrow encoding mismatch: Arrows are 1-indexed: 1 = Right, 2 = Left, 3 = Down, 4 = Up. Forgetting the offset when comparing
grid[r][c] == direction_indexcalculates incorrect edge costs.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Every cell's arrow tells you which neighbour to move to, following it is free, and you may "override" an arrow "at a cost of 1"; the question is the "fewest arrow overrides" to reach the far corner. That is a shortest path where each move costs 0 (follow the arrow) or 1 (change it): the need Zero-One BFS serves.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Read front to back, the distances the entries of dq had when they were pushed never decrease and differ by at most 1; an entry whose cell has since got a smaller dist is stale and changes nothing when popped. The decision: move to (nr, nc) only when dist[r][c] + weight < dist[nr][nc], where weight = 0 if grid[r][c] == sign else 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
No visited-on-enqueue set, as in plain BFS: a cell first reached by a 1-cost move can still get a smaller
distthrough a 0-cost move, so letdist[r][c] + weight < dist[nr][nc]decide.weight = 0 if grid[r][c] == sign else 1: the weight comes from the arrow of the cell you leave,grid[r][c], not the cell you enter, and signs are 1-4 in the order right, left, down, up (enumerate(moves, start=1)).dq.appendleftfor weight 0 anddq.appendfor weight 1: swapped, cells leave out of distance order and are pushed again and again (the finaldistis still right, but the linear bound is gone, and an early return at the corner would give a wrong answer), with no error.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Zero-One BFS. Each cell is a node, and a move to a neighbour costs zero if the cell's arrow already points there and one if I have to change the arrow. With only two weights I don't need Dijkstra's heap: I keep dist per cell and a deque. When a move gives a neighbour a smaller distance, I update it and push it to the front for a zero-cost move, or to the back for a one-cost move. So the deque always holds entries for just two distances, d at the front and d plus one behind them, and cells leave in the same order a heap would give. The trap is marking cells visited when I push them, like plain BFS: a cell first reached by a paid move can still get cheaper through a free one, so only the distance check decides. It's O(M times N) time and space, since each cell has at most four moves.
Complexity & Mathematical Proof
O(V + E)
Look at the code: a cell is pushed only when dist[r][c] + weight < dist[nr][nc] lowers its dist, and with 0/1 weights that happens at most twice per cell (first to d + 1, then at most once more to d), so while dq pops at most 2V entries. Each pop runs for sign, (dr, dc) in enumerate(moves, start=1) over 4 moves with O(1) work (bounds test, weight, one comparison, at most one push), and E ≤ 4V. Total: O(V + E) = O(M · N).
O(V)
dist holds one entry per cell, O(V), and dq holds at most two entries per cell, O(V). No recursion: the call stack is O(1). The input grid is not counted, and the answer is one integer.
T(V) ≤ 2V pops · 4 moves = 8V = O(V + E), V = M · N
Derivation Progression
if dist[r][c] + weight < dist[nr][nc]: ... ≤ 2 pushes per cell
Pops come out in non-decreasing distance order, so a cell's dist can drop at most twice (to d + 1, then to d): at most 2V pushes and 2V pops.
for sign, (dr, dc) in enumerate(moves, start=1): 4 moves
Each move is a bounds test, weight = 0 if grid[r][c] == sign else 1, one comparison and at most one appendleft or append, all O(1).
≤ 2V · 4 = 8V = O(V + E)
Multiplying the two bounds gives O(V + E) = O(M · N): the deque pops in O(1) where a heap would pay O(log V).
Variable Definitions
Number of rows in the grid
Number of columns in the grid
Number of cells, M · N
Number of moves between neighbouring cells, at most 4 · V
Memory Architecture & Bounds
O(1) (no recursion)
O(V): dist (V entries) and dq (at most 2V entries)
O(1): one integer
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "override" an arrow "at a cost of 1", following it is free, "fewest arrow overrides". A shortest path whose moves cost only 0 or 1: Zero-One BFS. At scale the same two-weight shape shows up wherever most steps are free and a few are charged, and it is worth spotting because the deque keeps the frontier in order without a heap.
cells and moves: at most pops of 4 moves each, about checks. dist is numbers; on a map with cells it would be the first thing to run out of memory, not the deque.
More than two weights (for example 0, 1 and 2) break the two-distance deque: that needs a bucket per distance (Dial's algorithm) or Dijkstra.
Core Algorithmic State Invariants
- The Answer Is Read After the Loop
The loop runs until dq is empty and then returns dist[m - 1][n - 1]. Every cell is reachable once arrows may change, so the corner always gets a finite distance; no -1 case exists in this problem.