Minimum Cost to Make at Least One Valid Path in a Grid
HardPrompt
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:
1which means go to the cell to the right. (i.e go fromgrid[i][j]togrid[i][j + 1])2which means go to the cell to the left. (i.e go fromgrid[i][j]togrid[i][j - 1])3which means go to the lower cell. (i.e go fromgrid[i][j]togrid[i + 1][j])4which means go to the upper cell. (i.e go fromgrid[i][j]togrid[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] <= 4
Approaches
3 approaches with complexity analysis and trade-offs.
This problem can be modeled as finding the shortest path in a weighted graph. The grid cells are the vertices, and possible moves between adjacent cells are the edges. A move that follows the grid's sign has a weight of 0, while a move that requires changing the sign has a weight of 1. The Bellman-Ford algorithm is a classic algorithm for finding the shortest paths from a single source vertex to all other vertices in a weighted digraph. While it's more general than needed here (it can handle negative edge weights), it provides a straightforward, albeit inefficient, solution.
Algorithm
- Initialize a
distarray of sizem x nwith infinity, and setdist[0][0] = 0. - Repeat
m * ntimes:- For each cell
(r, c)from(0, 0)to(m-1, n-1):- For each of the four possible directions
d(1 to 4):- Calculate the neighbor cell
(nr, nc). - If
(nr, nc)is within the grid boundaries:- Determine the
edge_cost: 0 ifdmatchesgrid[r][c], 1 otherwise. - Update the cost to the neighbor:
dist[nr][nc] = min(dist[nr][nc], dist[r][c] + edge_cost).
- Determine the
- Calculate the neighbor cell
- For each of the four possible directions
- For each cell
- Return
dist[m-1][n-1].
Walkthrough
We create a 2D array dist[m][n] to store the minimum cost to reach each cell (i, j) from the start (0, 0). Initialize all costs to infinity, except for dist[0][0], which is 0.
The algorithm works by repeatedly relaxing edges. We iterate m * n times (the total number of vertices). In each iteration, we traverse all cells (r, c) in the grid.
For each cell (r, c), we consider moving to its four neighbors (nr, nc).
The cost of an edge from (r, c) to (nr, nc) is 0 if the move aligns with the sign at grid[r][c], and 1 otherwise.
We "relax" the edge by updating the cost to the neighbor: dist[nr][nc] = min(dist[nr][nc], dist[r][c] + edge_cost).
After m * n - 1 iterations, dist[m-1][n-1] will hold the minimum cost to reach the destination. The extra iteration is to ensure convergence for the longest possible simple path.
The final answer is dist[m-1][n-1].
class Solution { public int minCost(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dist = new int[m][n]; for (int i = 0; i < m; i++) { java.util.Arrays.fill(dist[i], Integer.MAX_VALUE); } dist[0][0] = 0; int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // R, L, D, U -> map to 1, 2, 3, 4 boolean changed = true; // We can optimize by stopping if no distances change in an iteration. // A simple path has at most m*n-1 edges. for (int i = 0; i < m * n && changed; i++) { changed = false; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (dist[r][c] == Integer.MAX_VALUE) { continue; } for (int j = 0; j < 4; j++) { int nr = r + dirs[j][0]; int nc = c + dirs[j][1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) { int cost = (grid[r][c] == j + 1) ? 0 : 1; if (dist[r][c] + cost < dist[nr][nc]) { dist[nr][nc] = dist[r][c] + cost; changed = true; } } } } } } return dist[m - 1][n - 1]; }}Complexity
Time
`O((m*n)^2)`. The outer loop runs `m*n` times, and the inner loops iterate through all `m*n` cells and their 4 neighbors.
Space
`O(m*n)` to store the `dist` array.
Trade-offs
Pros
Relatively simple to understand and implement.
Correctly solves the problem.
Cons
Very inefficient due to its high time complexity. It re-evaluates all
m*ncells in each of them*niterations.
This approach treats the grid as a graph and applies Dijkstra's algorithm to find the shortest path from (0, 0) to (m-1, n-1). Dijkstra's algorithm is well-suited for finding the shortest paths in a graph with non-negative edge weights. It works by maintaining a set of visited vertices and iteratively selecting the unvisited vertex with the smallest known distance from the source.
Algorithm
- Initialize
dist[m][n]with infinity,dist[0][0] = 0. - Create a priority queue
pqand add(cost=0, row=0, col=0). - While
pqis not empty:- Extract the cell
(cost, r, c)with the minimum cost frompq. - If
cost > dist[r][c], continue. - If
(r, c)is the destination, returncost. - For each neighbor
(nr, nc)of(r, c):- Calculate
edge_cost(0 or 1). - If
cost + edge_cost < dist[nr][nc]:- Update
dist[nr][nc] = cost + edge_cost. - Add
(dist[nr][nc], nr, nc)topq.
- Update
- Calculate
- Extract the cell
Walkthrough
We use a priority queue to store tuples of (cost, row, col), ordered by cost. This ensures that we always explore the path with the minimum current cost.
A dist[m][n] array is used to keep track of the minimum cost to reach each cell. It's initialized with infinity, and dist[0][0] is set to 0.
We start by adding (0, 0, 0) to the priority queue.
While the priority queue is not empty, we extract the element (cost, r, c) with the smallest cost.
If this cost is greater than the already known minimum cost to reach (r, c) (i.e., cost > dist[r][c]), we skip it, as we've found a better path already.
If we reach the destination (m-1, n-1), we return the current cost.
For the current cell (r, c), we explore its four neighbors (nr, nc).
For each neighbor, we calculate the cost of the move. The cost is 0 if the move follows the direction specified in grid[r][c], and 1 otherwise.
The new cost to reach the neighbor is cost + edge_cost.
If this new cost is less than dist[nr][nc], we update dist[nr][nc] and add (new_cost, nr, nc) to the priority queue.
class Solution { public int minCost(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dist = new int[m][n]; for (int i = 0; i < m; i++) { java.util.Arrays.fill(dist[i], Integer.MAX_VALUE); } // PriorityQueue stores {cost, row, col} java.util.PriorityQueue<int[]> pq = new java.util.PriorityQueue<>((a, b) -> a[0] - b[0]); dist[0][0] = 0; pq.offer(new int[]{0, 0, 0}); int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // R, L, D, U while (!pq.isEmpty()) { int[] curr = pq.poll(); int cost = curr[0]; int r = curr[1]; int c = curr[2]; if (cost > dist[r][c]) { continue; } if (r == m - 1 && c == n - 1) { return cost; } for (int i = 0; i < 4; i++) { int nr = r + dirs[i][0]; int nc = c + dirs[i][1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) { int edgeCost = (grid[r][c] == i + 1) ? 0 : 1; int newCost = cost + edgeCost; if (newCost < dist[nr][nc]) { dist[nr][nc] = newCost; pq.offer(new int[]{newCost, nr, nc}); } } } } return -1; // Should not be reached }}Complexity
Time
`O(m*n * log(m*n))`. There are `m*n` vertices and at most `4*m*n` edges. Each push and pop operation on the priority queue takes `O(log(m*n))` time.
Space
`O(m*n)` for the `dist` array and the priority queue, which can store up to all `m*n` cells in the worst case.
Trade-offs
Pros
Significantly more efficient than the Bellman-Ford approach.
A standard and well-known algorithm for shortest path problems.
Cons
The
log(V)factor from the priority queue operations makes it slightly less efficient than specialized algorithms for graphs with only 0/1 edge weights.
This is the most efficient approach for this problem. Since the edge weights are restricted to only 0 and 1, we can optimize Dijkstra's algorithm by replacing the priority queue with a double-ended queue (deque). This specialized version of BFS, often called 0-1 BFS, processes nodes in increasing order of cost without the logarithmic overhead of a priority queue.
Algorithm
- Initialize
dist[m][n]with infinity,dist[0][0] = 0. - Create a deque and add
(0, 0)to the front. - While the deque is not empty:
- Remove cell
(r, c)from the front of the deque. - For each neighbor
(nr, nc)of(r, c):- Calculate
edge_cost(0 or 1). - If
dist[r][c] + edge_cost < dist[nr][nc]:- Update
dist[nr][nc] = dist[r][c] + edge_cost. - If
edge_costis 0, add(nr, nc)to the front of the deque. - If
edge_costis 1, add(nr, nc)to the back of the deque.
- Update
- Calculate
- Remove cell
- Return
dist[m-1][n-1].
Walkthrough
The core idea is to maintain the elements in the deque such that they are sorted by cost. We can achieve this because new paths are either of the same cost (from a 0-cost edge) or cost + 1 (from a 1-cost edge).
We use a dist[m][n] array, initialized to infinity, with dist[0][0] = 0.
We use a deque and add the starting cell (0, 0) to it.
While the deque is not empty, we remove a cell (r, c) from the front.
For each of its four neighbors (nr, nc):
Calculate the edge_cost. It's 0 if the move follows the sign grid[r][c], and 1 otherwise.
Calculate the new_cost = dist[r][c] + edge_cost.
If new_cost is less than the current dist[nr][nc]:
Update dist[nr][nc] = new_cost.
If the edge_cost was 0, we add the neighbor (nr, nc) to the front of the deque. This is because we want to explore these 0-cost paths immediately, as they don't increase the total cost.
If the edge_cost was 1, we add the neighbor (nr, nc) to the back of the deque. These paths have a higher cost and should be explored after all current lower-cost paths.
This process ensures that we always explore cells in non-decreasing order of their costs from the source. The final answer is dist[m-1][n-1].
class Solution { public int minCost(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dist = new int[m][n]; for (int i = 0; i < m; i++) { java.util.Arrays.fill(dist[i], Integer.MAX_VALUE); } // Deque stores {row, col} java.util.Deque<int[]> deque = new java.util.ArrayDeque<>(); dist[0][0] = 0; deque.offerFirst(new int[]{0, 0}); int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // R, L, D, U while (!deque.isEmpty()) { int[] curr = deque.pollFirst(); int r = curr[0]; int c = curr[1]; int cost = dist[r][c]; if (r == m - 1 && c == n - 1) { return cost; } for (int i = 0; i < 4; i++) { int nr = r + dirs[i][0]; int nc = c + dirs[i][1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) { int edgeCost = (grid[r][c] == i + 1) ? 0 : 1; int newCost = cost + edgeCost; if (newCost < dist[nr][nc]) { dist[nr][nc] = newCost; if (edgeCost == 0) { deque.offerFirst(new int[]{nr, nc}); } else { deque.offerLast(new int[]{nr, nc}); } } } } } return -1; // Should not be reached }}Complexity
Time
`O(m*n)`. Each cell is added to and removed from the deque exactly once. All operations (add/remove from front/back, neighbor checks) are `O(1)`.
Space
`O(m*n)` for the `dist` array and the deque, which can store up to all `m*n` cells.
Trade-offs
Pros
Optimal time complexity for this problem.
Avoids the logarithmic factor of a priority queue, making it faster than standard Dijkstra's.
Cons
Slightly more complex to reason about than standard Dijkstra's if unfamiliar with the 0-1 BFS pattern.
Solutions
Solution
class Solution { public int minCost ( int [][] grid ) { int m = grid . length , n = grid [ 0 ]. length ; boolean [][] vis = new boolean [ m ][ n ]; Deque < int []> q = new ArrayDeque <>(); q . offer ( new int [] { 0 , 0 , 0 }); int [][] dirs = { { 0 , 0 }, { 0 , 1 }, { 0 , - 1 }, { 1 , 0 }, {- 1 , 0 } }; while (! q . isEmpty ()) { int [] p = q . poll (); int i = p [ 0 ], j = p [ 1 ], d = p [ 2 ]; if ( i == m - 1 && j == n - 1 ) { return d ; } if ( vis [ i ][ j ]) { continue ; } vis [ i ][ j ] = true ; for ( int k = 1 ; k <= 4 ; ++ k ) { int x = i + dirs [ k ][ 0 ], y = j + dirs [ k ][ 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n ) { if ( grid [ i ][ j ] == k ) { q . offerFirst ( new int [] { x , y , d }); } else { q . offer ( new int [] { x , y , d + 1 }); } } } } return - 1 ; } }class Solution { public: int minCost ( vector < vector < int >>& grid ) { int m = grid . size (), n = grid [ 0 ]. size (); vector < vector < bool >> vis ( m , vector < bool > ( n )); vector < vector < int >> dirs = { { 0 , 0 }, { 0 , 1 }, { 0 , - 1 }, { 1 , 0 }, { - 1 , 0 } }; deque < pair < int , int >> q ; q . push_back ({ 0 , 0 }); while ( ! q . empty ()) { auto p = q . front (); q . pop_front (); int i = p . first / n , j = p . first % n , d = p . second ; if ( i == m - 1 && j == n - 1 ) return d ; if ( vis [ i ][ j ]) continue ; vis [ i ][ j ] = true ; for ( int k = 1 ; k <= 4 ; ++ k ) { int x = i + dirs [ k ][ 0 ], y = j + dirs [ k ][ 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n ) { if ( grid [ i ][ j ] == k ) q . push_front ({ x * n + y , d }); else q . push_back ({ x * n + y , d + 1 }); } } } return - 1 ; } };class Solution : def minCost ( self , grid : List [ List [ int ]]) -> int : m , n = len ( grid ), len ( grid [ 0 ]) dirs = [[ 0 , 0 ], [ 0 , 1 ], [ 0 , - 1 ], [ 1 , 0 ], [ - 1 , 0 ]] q = deque ([( 0 , 0 , 0 )]) vis = set () while q : i , j , d = q . popleft () if ( i , j ) in vis : continue vis . add (( i , j )) if i == m - 1 and j == n - 1 : return d for k in range ( 1 , 5 ): x , y = i + dirs [ k ][ 0 ], j + dirs [ k ][ 1 ] if 0 <= x < m and 0 <= y < n : if grid [ i ][ j ] == k : q . appendleft (( x , y , d )) else : q . append (( x , y , d + 1 )) return - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.