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] <= 4Problem Overview: You get an m x n grid where each cell contains a direction (right, left, down, up). Following the direction costs 0, but changing it costs 1. The goal is to reach the bottom-right cell from the top-left with the minimum total modification cost.
The grid naturally forms a directed graph: every cell has an outgoing edge based on its arrow. Moving in the indicated direction costs 0, while moving to any other neighbor requires paying 1 to change the sign. The task becomes a classic shortest path problem on a weighted grid graph.
Approach 1: Dijkstra-like BFS Using Priority Queue (O(mn log(mn)) time, O(mn) space)
Treat each cell as a node in a graph and run Dijkstra’s algorithm. From each position, explore the four neighbors. If the move matches the arrow in the current cell, the cost stays the same; otherwise add 1. A min-heap (priority queue) always expands the cell with the lowest accumulated cost. Maintain a dist matrix to store the minimum cost seen for each cell and skip states that are already improved. This works because all edge weights are non‑negative. The algorithm guarantees the first time you pop the destination from the heap, you have the optimal cost.
This method is essentially shortest path on a graph represented by a matrix. It is the most intuitive approach when you recognize the weighted edges. Works well even for the largest constraints.
Approach 2: Bellman-Ford-like Relaxation (O(mn * 4 * iterations) time, O(mn) space)
Instead of using a priority queue, repeatedly relax edges across the grid. Initialize the cost of the start cell as 0 and all others as infinity. For each cell, check its four neighbors and update their cost using the same rule: +0 if the arrow matches, +1 otherwise. Continue relaxing until no updates occur or until the grid stabilizes. This mirrors the Bellman-Ford process of relaxing edges until shortest paths converge.
This version is easier to implement in languages where priority queues are slower or when you want a straightforward dynamic relaxation loop. It still models the problem as a shortest-path computation but without the heap optimization.
Conceptually, both approaches rely on graph traversal and shortest path relaxation techniques. Understanding how the grid becomes a graph is key. Many candidates also frame the optimal solution as a variation of Breadth-First Search where zero-cost edges are prioritized.
Recommended for interviews: The Dijkstra-like BFS with a priority queue is the expected solution. It clearly models the grid as a weighted graph and runs in O(mn log(mn)). Explaining the relaxation idea first shows you understand shortest-path fundamentals, while implementing the heap-based solution demonstrates practical algorithm skill.
This approach involves using a priority queue to keep track of the cells to explore, always picking the cell from the queue that has the lowest cost accumulated so far. The grid is effectively treated as a graph where each cell represents a node, and moving from one cell to an adjacent one (in the direction indicated by the cell) is a free edge with cost 0, whereas changing direction is an edge with cost 1.
The solution uses BFS with a double-ended queue (deque) to explore the grid. The key idea is to prioritize cells that can be reached with the smallest cost. Here, we use the deque to achieve '0-cost moves' immediately with appendleft, and '1-cost moves' at a later stage with append.
Time complexity is O(m*n), where m and n are the dimensions of the grid, due to each cell being processed in constant time with respect to its neighbors. Space complexity is also O(m*n) due to the storage required for maintaining the costs of each cell.
This approach employs a relaxation technique similar to the Bellman-Ford algorithm. We repeatedly relax the cost to reach each cell to find the shortest path from (0, 0) to (m-1, n-1). This is a valid approach due to the finite grid size and known possible transitions.
This solution applies a priority queue to relax the path cost, similar to the Bellman-Ford technique. Each grid cell is checked for possible direction changes, and the priority queue sorts cells based on their path cost, ensuring the optimal cost transit is prioritized.
Time complexity is O(m * n * log(m * n)), similar to Dijkstra’s execution over a grid, and space complexity is O(m * n) due to the cost matrix and priority queue storage.
This problem is essentially a shortest path model, but what we are looking for is the minimum number of direction changes.
In an undirected graph where the edge weights are only 0 and 1, we can use a double-ended queue for BFS. The principle is that when the weight of the point that can be expanded currently is 0, it is added to the front of the queue; when the weight is 1, it is added to the end of the queue.
If the weight of an edge is 0, then the weight of the newly expanded node is the same as the weight of the current queue head node. Obviously, it can be used as the starting point for the next expansion.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dijkstra-like BFS Using Priority Queue | Time complexity is O(m*n), where m and n are the dimensions of the grid, due to each cell being processed in constant time with respect to its neighbors. Space complexity is also O(m*n) due to the storage required for maintaining the costs of each cell. |
| Bellman-Ford-like Relaxation Approach | Time complexity is O(m * n * log(m * n)), similar to Dijkstra’s execution over a grid, and space complexity is O(m * n) due to the cost matrix and priority queue storage. |
| Double-ended Queue BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra-like BFS with Priority Queue | O(mn log(mn)) | O(mn) | Best general solution for weighted grid shortest path problems |
| Bellman-Ford-style Relaxation | O(mn * iterations) | O(mn) | Simpler implementation when repeatedly relaxing edges without a heap |
Minimum Cost to Make at Least One Valid Path in a Grid - Leetcode 1368 - Python • NeetCodeIO • 13,077 views views
Watch 9 more video solutions →Practice Minimum Cost to Make at Least One Valid Path in a Grid with our built-in code editor and test cases.
Practice on FleetCode