Scale Engineer

Minimum Cost to Make at Least One Valid Path in a Grid

Hard
#1269Time: `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.1 company
Algorithms
Breadth-First SearchShortest Path
Data structures
ArrayHeap (Priority Queue)MatrixGraph
Companies
Cleartrip

Prompt

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.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • 1 <= 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 dist array of size m x n with infinity, and set dist[0][0] = 0.
  • Repeat m * n times:
    • 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 if d matches grid[r][c], 1 otherwise.
          • Update the cost to the neighbor: dist[nr][nc] = min(dist[nr][nc], dist[r][c] + edge_cost).
  • 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*n cells in each of the m*n iterations.

Solutions

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 ; } }

Video 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.

← Previous

Previous problem

Next →

Next problem