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

Hard
1570.

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

Minimum Cost to Make at Least One Valid Path in a Grid is a hard coding problem on matrix, breadth-first search and graph, asked in Amazon and Google interviews.

Every cell of the m x n matrix grid holds a sign pointing to the next cell to visit:

  • 1 — go right, to (i, j + 1);
  • 2 — go left, to (i, j - 1);
  • 3 — go down, to (i + 1, j);
  • 4 — go up, to (i - 1, j).

Some signs may point outside the grid. Starting at (0, 0) and following the signs gives a path; it is valid if it reaches (m - 1, n - 1).

You may change the sign of any cell for a cost of 1 (each cell's sign at most once). Return the minimum total cost needed to make the grid contain at least one valid path.

Example 1

Input
grid = [[1,1,3],[2,2,3],[4,4,1]]
Output
0
Explanation
Right, right, down, down already reaches the bottom-right corner.

Example 2

Input
grid = [[2,2],[2,2]]
Output
2
Explanation
Every sign points left; at least two of them must be changed, e.g. `(0,0)` to right and `(0,1)` to down.

Example 3

Input
grid = [[1,4],[1,1]]
Output
1

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • 1 <= grid[i][j] <= 4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minCost = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Minimum Cost to Make at Least One Valid Path in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Cost to Make at Least One Valid Path in a Grid is a hard coding problem on matrix, breadth-first search and graph, asked in Amazon and Google interviews.

Problem statement

Every cell of the m x n matrix grid holds a sign pointing to the next cell to visit:

  • 1 — go right, to (i, j + 1);
  • 2 — go left, to (i, j - 1);
  • 3 — go down, to (i + 1, j);
  • 4 — go up, to (i - 1, j).

Some signs may point outside the grid. Starting at (0, 0) and following the signs gives a path; it is valid if it reaches (m - 1, n - 1).

You may change the sign of any cell for a cost of 1 (each cell's sign at most once). Return the minimum total cost needed to make the grid contain at least one valid path.

Example 1

Input: grid = [[1,1,3],[2,2,3],[4,4,1]]
Output: 0
Explanation: Right, right, down, down already reaches the bottom-right corner.

Example 2

Input: grid = [[2,2],[2,2]]
Output: 2
Explanation: Every sign points left; at least two of them must be changed, e.g. `(0,0)` to right and `(0,1)` to down.

Example 3

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

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • 1 <= grid[i][j] <= 4

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

  1. Hint 1

    Model each cell as a node with an edge to each of its up to four neighbours.

  2. Hint 2

    The edge in the sign's direction is free; every other edge costs 1 (changing the sign). The answer is the cheapest path from the start to the corner.

  3. Hint 3

    With edge weights 0 and 1, a 0-1 BFS (deque: free edges to the front, paid edges to the back) finds shortest paths in linear time.

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

Changing a sign is the same as taking a cost-1 edge out of that cell, so the task is a shortest path in a graph whose edges weigh 0 (follow the sign) or 1 (go elsewhere) — a 0-1 BFS.

Approach

  1. Set dist[0][0] = 0 and all other distances to infinity; process cells in order of distance.
  2. Pop the cell with the smallest distance d (a deque or two buckets — d and d + 1 — suffice). Skip it if already finalised.
  3. For each of the four directions, the neighbour costs d if the cell's sign points there and d + 1 otherwise; relax it, pushing free moves into the current bucket and paid moves into the next.
  4. Return dist[m-1][n-1] when the corner is finalised.

Why it works

A path that follows signs except at c cells costs exactly c, and changing a cell's sign twice never helps on a shortest path because a shortest path never revisits a cell. So the minimum cost equals the shortest-path distance with 0/1 weights, and 0-1 BFS is Dijkstra specialised to those weights — cells leave the buckets in non-decreasing distance order.

Complexity

  • Time — O(m · n)
  • Space — O(m · n)

Pitfalls

  • A plain BFS that counts edges ignores the free moves; the weights matter.
  • Free moves must be processed before paid ones of the same layer — push them to the front of the deque (or into the current bucket).
  • A 1 × 1 grid costs 0 whatever its sign.

Reference solution

Python

from typing import List
from collections import deque

def minCost(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    moves = {1: (0, 1), 2: (0, -1), 3: (1, 0), 4: (-1, 0)}
    INF = float('inf')
    dist = [[INF] * n for _ in range(m)]
    dist[0][0] = 0
    dq = deque([(0, 0)])
    while dq:
        r, c = dq.popleft()
        d = dist[r][c]
        for sign, (dr, dc) in moves.items():
            a, b = r + dr, c + dc
            if 0 <= a < m and 0 <= b < n:
                w = 0 if grid[r][c] == sign else 1
                if d + w < dist[a][b]:
                    dist[a][b] = d + w
                    if w == 0:
                        dq.appendleft((a, b))
                    else:
                        dq.append((a, b))
    return dist[m - 1][n - 1]

Java

public static int minCost(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] DR = {0, 0, 0, 1, -1}, DC = {0, 1, -1, 0, 0};
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    dist[0][0] = 0;
    ArrayDeque<int[]> dq = new ArrayDeque<>();
    dq.add(new int[]{0, 0});
    while (!dq.isEmpty()) {
        int[] cur = dq.pollFirst();
        int r = cur[0], c = cur[1], d0 = dist[r][c];
        for (int d = 1; d <= 4; d++) {
            int a = r + DR[d], b = c + DC[d];
            if (a < 0 || b < 0 || a >= m || b >= n) continue;
            int w = grid[r][c] == d ? 0 : 1;
            if (d0 + w < dist[a][b]) {
                dist[a][b] = d0 + w;
                if (w == 0) dq.addFirst(new int[]{a, b});
                else dq.addLast(new int[]{a, b});
            }
        }
    }
    return dist[m - 1][n - 1];
}

C++

int minCost(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int DR[5] = {0, 0, 0, 1, -1}, DC[5] = {0, 1, -1, 0, 0};
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
    dist[0][0] = 0;
    deque<pair<int, int>> dq;
    dq.push_back({0, 0});
    while (!dq.empty()) {
        auto cur = dq.front();
        dq.pop_front();
        int r = cur.first, c = cur.second, d0 = dist[r][c];
        for (int d = 1; d <= 4; d++) {
            int a = r + DR[d], b = c + DC[d];
            if (a < 0 || b < 0 || a >= m || b >= n) continue;
            int w = grid[r][c] == d ? 0 : 1;
            if (d0 + w < dist[a][b]) {
                dist[a][b] = d0 + w;
                if (w == 0) dq.push_front({a, b});
                else dq.push_back({a, b});
            }
        }
    }
    return dist[m - 1][n - 1];
}

JavaScript

var minCost = function(grid) {
    var m = grid.length, n = grid[0].length, total = m * n;
    var DR = [0, 0, 0, 1, -1], DC = [0, 1, -1, 0, 0];
    var dist = new Array(total).fill(Infinity), done = new Array(total).fill(false);
    dist[0] = 0;
    var cur = [0];
    for (var level = 0; cur.length > 0; level++) {
        var next = [];
        while (cur.length > 0) {
            var u = cur.pop();
            if (done[u]) continue;
            done[u] = true;
            if (u === total - 1) return level;
            var r = Math.floor(u / n), c = u % n;
            for (var d = 1; d <= 4; d++) {
                var a = r + DR[d], b = c + DC[d];
                if (a < 0 || b < 0 || a >= m || b >= n) continue;
                var v = a * n + b, w = grid[r][c] === d ? 0 : 1;
                if (level + w < dist[v]) {
                    dist[v] = level + w;
                    if (w === 0) cur.push(v); else next.push(v);
                }
            }
        }
        cur = next;
    }
    return dist[total - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 184 matrix problems · the whole catalogue

Learn the technique: Matrix and Grid Traversal · Breadth-First Search (BFS)