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

Problem

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.

Examples

Example 1:

$$ \begin{matrix} \rightarrow & \rightarrow & \rightarrow & \rightarrow \\ \leftarrow & \leftarrow & \leftarrow & \leftarrow \\ \rightarrow & \rightarrow & \rightarrow & \rightarrow \\ \leftarrow & \leftarrow & \leftarrow & \leftarrow \\ \end{matrix} $$

1
2
3
4
5


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:

$$ \begin{matrix} \rightarrow & \rightarrow & \downarrow \\ \downarrow & \leftarrow & \leftarrow \\ \rightarrow & \rightarrow & \uparrow \\ \end{matrix} $$

1
2
3


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:

$$ \begin{matrix} \rightarrow & \leftarrow \\ \uparrow & \downarrow \\ \end{matrix} $$

1
2


Input: grid = [[1,2],[4,3]]
Output: 1

Solution

Method 1 - Using Dijkstra Algorithm

To solve the problem of finding the minimum cost to make the grid have at least one valid path, we can use a shortest path algorithm like Dijkstra’s but slightly modified. The grid can be considered as a weighted graph where:

Nodes represent grid cells.
Edges between nodes represent possible moves between cells, with weights being the cost of modifying the signs.

Approach

Define the direction vectors for moving right, left, down, and up.
Use a priority queue (min-heap) to always expand the least cost cell first.
Initialise the distance to reach each cell as infinity, except for the starting cell which is 0.
Use the priority queue to explore the neighbors of the current cell.
Calculate the cost to move to each neighbor. If it follows the current cell’s direction, the cost is 0, otherwise it is 1.
Update the distance and push the neighbor to the queue if a shorter path is found.
Continue until reaching the bottom-right cell.
The final answer will be the distance to the bottom-right cell.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[0][0] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, 0, 0});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int cost = curr[0], i = curr[1], j = curr[2];
            
            if (i == m - 1 && j == n - 1) {
                return cost;
            }
            
            for (int idx = 0; idx < 4; idx++) {
                int ni = i + directions[idx][0], nj = j + directions[idx][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                    int newCost = cost + (grid[i][j] != idx + 1 ? 1 : 0);
                    if (newCost < dist[ni][nj]) {
                        dist[ni][nj] = newCost;
                        pq.offer(new int[]{newCost, ni, nj});
                    }
                }
            }
        }
        
        return dist[m - 1][n - 1];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        pq: List[Tuple[int, int, int]] = [(0, 0, 0)]  # (cost, row, col)
        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = 0
        
        while pq:
            cost, i, j = heappop(pq)
            
            if (i, j) == (m - 1, n - 1):
                return cost
            
            for idx, (di, dj) in enumerate(directions):
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n:
                    new_cost = cost + (grid[i][j] != idx + 1)
                    if new_cost < dist[ni][nj]:
                        dist[ni][nj] = new_cost
                        heappush(pq, (new_cost, ni, nj))
        
        return dist[m - 1][n - 1]

Complexity

⏰ Time complexity: O(m * n * log(m * n)) due to the use of a priority queue where every node is processed once.
🧺 Space complexity: O(m * n) for storing distances and the priority queue.

Problem#

Examples#

Solution#

Method 1 - Using Dijkstra Algorithm#

Approach#

Code#

Complexity#