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

frequently reported atGoogle

the problem

In plain words

Each cell has a sign: 1 → right, 2 → left, 3 → down, 4 → up. From (0, 0) you follow signs for free. Changing a cell's sign costs 1 (once per cell). Return the minimum total cost so that some path reaches the bottom-right cell.

in grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]

out 3

Change three signs to step down at the ends of rows.

in grid = [[1,1,3],[3,2,2],[1,1,4]]

out 0

Following signs already reaches the corner.

in grid = [[1,2],[4,3]]

out 1

1 ≤ m, n ≤ 100
1 ≤ grid[i][j] ≤ 4

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

pattern0-1 BFS Dijkstra

Moving the way the arrow points costs 0; any other direction costs 1 (you change that arrow). A graph with weights 0 and 1 → 0-1 BFS.

solutions

From brute force to optimal

Each cell has 4 outgoing edges: weight 0 for its sign's direction, 1 for the rest. Run Dijkstra.

cost[0][0] = 0, heap {0, 0, 0}.
Poll, skip stale, relax 4 neighbours with step 0 or 1.
Return cost of the corner.

timeO(mn · log(mn))

4mn edges, each push O(log mn).

spaceO(mn)

cost grid and heap.

javajava.util.*

1class Solution {2    // Sign 1 = right, 2 = left, 3 = down, 4 = up: DIRS[s - 1] is the move sign s points to.3    private static final int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};4 5    public int minCost(int[][] grid) {6        int rows = grid.length, cols = grid[0].length;7        int[][] cost = new int[rows][cols];8        for (int[] row : cost) Arrays.fill(row, Integer.MAX_VALUE);9        cost[0][0] = 0;10        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));11        pq.offer(new int[] {0, 0, 0});                  // {cost, row, col}12        while (!pq.isEmpty()) {13            int[] top = pq.poll();14            int d = top[0], r = top[1], c = top[2];15            if (d > cost[r][c]) continue;16            for (int s = 0; s < 4; s++) {17                int nr = r + DIRS[s][0], nc = c + DIRS[s][1];18                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;19                int step = grid[r][c] == s + 1 ? 0 : 1;   // follow the sign for free, else pay 120                if (d + step < cost[nr][nc]) {21                    cost[nr][nc] = d + step;22                    pq.offer(new int[] {d + step, nr, nc});23                }24            }25        }26        return cost[rows - 1][cols - 1];27    }28}

Same graph, but weights are only 0/1: a deque replaces the heap.

Deque starts with (0,0).
Pop front; for each direction: free move → offerFirst, paid move → offerLast (if it improves).
Return cost of the corner.

timeO(mn)

Each cell is pushed at most twice; 4 edges per cell.

spaceO(mn)

cost grid and deque.

javajava.util.*

1class Solution {2    // Sign 1 = right, 2 = left, 3 = down, 4 = up: DIRS[s - 1] is the move sign s points to.3    private static final int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};4 5    public int minCost(int[][] grid) {6        int rows = grid.length, cols = grid[0].length;7        int[][] cost = new int[rows][cols];8        for (int[] row : cost) Arrays.fill(row, Integer.MAX_VALUE);9        cost[0][0] = 0;10        Deque<int[]> deque = new ArrayDeque<>();11        deque.offerFirst(new int[] {0, 0});12        while (!deque.isEmpty()) {13            int[] cur = deque.pollFirst();14            int r = cur[0], c = cur[1];15            for (int s = 0; s < 4; s++) {16                int nr = r + DIRS[s][0], nc = c + DIRS[s][1];17                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;18                int step = grid[r][c] == s + 1 ? 0 : 1;19                if (cost[r][c] + step < cost[nr][nc]) {20                    cost[nr][nc] = cost[r][c] + step;21                    if (step == 0) deque.offerFirst(new int[] {nr, nc}); // free move → front22                    else deque.offerLast(new int[] {nr, nc});            // paid move → back23                }24            }25        }26        return cost[rows - 1][cols - 1];27    }28}

in the room

How to say it in the interview

talk track

Reframe first: "changing a sign = paying 1 to move in a different direction."
Then: 0/1 weights → 0-1 BFS, O(mn).

traps

Mixing up the sign order — 1 right, 2 left, 3 down, 4 up.
Thinking you need to actually modify the grid; you never do.

what they ask next

Follow-ups

Arbitrary change costs per cell?

Weights are no longer 0/1 → switch back to Dijkstra.

before you submit

Edge cases to test

1 × 1 grid → 0.
Signs that point off the grid or around in a loop: you must pay to leave.
Sign order is 1 right, 2 left, 3 down, 4 up — mixing it up silently gives wrong answers.

practise next