Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:
1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])Notice that there could be some signs on the cells of the grid that point outside the grid.
You will initially start at the upper left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path does not have to be the shortest.
You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.
Return the minimum cost to make the grid have at least one valid path.
Example 1:
Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]] Output: 3 Explanation: You will start at point (0, 0). The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3) The total cost = 3.
Example 2:
Input: grid = [[1,1,3],[3,2,2],[1,1,4]] Output: 0 Explanation: You can follow the path from (0, 0) to (2, 2).
Example 3:
Input: grid = [[1,2],[4,3]] Output: 1
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1001 <= grid[i][j] <= 4In #1368 Minimum Cost to Make at Least One Valid Path in a Grid, each cell contains a direction indicating where you should move next. Following the indicated direction has 0 cost, while changing direction requires a cost of 1. The goal is to reach the bottom-right cell from the top-left with the minimum modification cost.
This problem can be modeled as a shortest path problem on a grid graph. A very effective strategy is 0-1 BFS using a deque. When moving in the cell’s suggested direction, push the next cell to the front (cost 0); when modifying the direction, push it to the back (cost 1). This ensures nodes are processed in increasing cost order without a full priority queue.
Alternatively, you can treat the grid as a weighted graph and apply Dijkstra’s algorithm with a priority_queue. Both approaches compute the minimum cost to reach every cell, with the optimal answer found at the destination cell.
The solution efficiently explores the grid while maintaining the minimum accumulated cost.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| 0-1 BFS with Deque | O(m × n) | O(m × n) |
| Dijkstra with Priority Queue | O(m × n log(m × n)) | O(m × n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Build a graph where grid[i][j] is connected to all the four side-adjacent cells with weighted edge. the weight is 0 if the sign is pointing to the adjacent cell or 1 otherwise.
Do BFS from (0, 0) visit all edges with weight = 0 first. the answer is the distance to (m -1, n - 1).
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, grid-based shortest path problems like this are common in FAANG-style interviews. They test understanding of graph modeling, BFS variants like 0-1 BFS, and shortest-path algorithms.
A deque is ideal when implementing the 0-1 BFS approach. It allows pushing zero-cost transitions to the front and cost-one transitions to the back, ensuring efficient shortest-path traversal.
Yes, Dijkstra’s algorithm can also be used by treating each cell as a node and direction changes as weighted edges. Using a priority queue ensures the minimum cost path is found correctly.
The most efficient approach is 0-1 BFS. Since moves either cost 0 (following the given direction) or 1 (changing direction), a deque can process nodes in increasing cost order without using a full priority queue.