Minimum Cost Grid Traversal with Directional Constraints

Problem Statement

You are given an m x n grid where each cell contains a direction indicator:

• 1 = right
• 2 = left
• 3 = down
• 4 = up

From any cell, moving in the cell's preferred direction costs 0; moving in any other of the four cardinal directions costs 1. Find the minimum total cost to travel from (0, 0) to (m-1, n-1).

(This is essentially LC 1368 — Minimum Cost to Make at Least One Valid Path in a Grid.)

Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: Flip the arrow in three cells to carve a valid path.

Example 2:

Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: A path already exists following the arrows.

Constraints:

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

Difficulty: Hard

---

Pattern Recognition

• What is the structure of the input? A grid whose cells encode preferred outgoing direction.
• What are we optimizing? Shortest path from top-left to bottom-right where edges have weight 0 (matches arrow) or 1 (otherwise).
• What pattern does this suggest? 0/1 Dijkstra using a deque.
• Why does this pattern fit? Edges are binary (0 or 1), and the arrow means you can follow an entire pre-existing chain of matching directions for free.

---

Approach

Brute Force — Dijkstra with min-heap

Fine correctness-wise; wastes a log factor.

Time: O(mn log mn). Space: O(mn). Why insufficient: Same story as the obstacle-removal problem — binary weights don't need a heap.

Optimal — 0/1 Deque BFS

Key Insight: The arrow matching turns the problem into a 0/1 weighted shortest path. Push zero-cost neighbors (arrow direction) to the front of the deque, and one-cost neighbors (other three directions) to the back. Dijkstra correctness without the heap log.

Step-by-step:

1. dist[0][0] = 0, everything else infinity.
2. Deque starts with [(0, 0)].
3. Pop the front. For each of the four directions d (1..4):
   • (nr, nc) the neighbor in direction d. Skip out-of-bounds.
   • cost = (grid[r][c] == d) ? 0 : 1.
   • If dist[r][c] + cost < dist[nr][nc]: update, push front if cost 0, back if cost 1.
4. Return dist[m-1][n-1].

Time: O(mn). Space: O(mn).

---

Walkthrough

grid = [[1,1,3],[3,2,2],[1,1,4]]. Target (2,2).

Direction mapping: 1=right, 2=left, 3=down, 4=up.

Path check: (0,0) arrow right -> (0,1) arrow right -> (0,2) arrow down -> (1,2) arrow left -> (1,1) arrow left -> (1,0) arrow down -> (2,0) arrow right -> (2,1) arrow right -> (2,2). All edges cost 0.

Answer: 0.

Let's trace a few early pops:

Pop	Arrow	0-cost push	1-cost pushes	Deque head
(0,0)	1=right	(0,1) with dist 0, front	(1,0) back	(0,1)
(0,1)	1=right	(0,2) with dist 0, front	others back	(0,2)
(0,2)	3=down	(1,2) with dist 0, front	(0,1) better? no	(1,2)
(1,2)	2=left	(1,1) with dist 0, front	...	(1,1)
... chain continues until (2,2) with dist 0

---

Implementation

TypeScript

// grid[r][c] in {1,2,3,4} = {right, left, down, up}
function minCost(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const dist: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(Infinity));
  dist[0][0] = 0;
  const deque: Array<[number, number]> = [[0, 0]];
  // index 0 unused; 1=right, 2=left, 3=down, 4=up
  const dirs: Record<number, [number, number]> = {
    1: [0, 1], 2: [0, -1], 3: [1, 0], 4: [-1, 0],
  };

  while (deque.length > 0) {
    const [r, c] = deque.shift()!;
    for (let d = 1; d <= 4; d++) {
      const [dr, dc] = dirs[d];
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
      const cost = grid[r][c] === d ? 0 : 1;
      if (dist[r][c] + cost < dist[nr][nc]) {
        dist[nr][nc] = dist[r][c] + cost;
        if (cost === 0) deque.unshift([nr, nc]);
        else deque.push([nr, nc]);
      }
    }
  }
  return dist[rows-1][cols-1];
}

C++

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
        dist[0][0] = 0;
        deque<pair<int,int>> dq;
        dq.push_front({0, 0});
        int dr[5] = {0, 0, 0, 1, -1};
        int dc[5] = {0, 1, -1, 0, 0};
        while (!dq.empty()) {
            auto [r, c] = dq.front(); dq.pop_front();
            for (int d = 1; d <= 4; ++d) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                int cost = grid[r][c] == d ? 0 : 1;
                if (dist[r][c] + cost < dist[nr][nc]) {
                    dist[nr][nc] = dist[r][c] + cost;
                    if (cost == 0) dq.push_front({nr, nc});
                    else dq.push_back({nr, nc});
                }
            }
        }
        return dist[rows-1][cols-1];
    }
};

Watch out: Mixing up the direction encoding. Lay out your dir table explicitly (1=right, 2=left, 3=down, 4=up) and match it to dr/dc.

Watch out: Popping from the back by mistake. Always pop the deque's front.

Watch out: Updating dist without the strict-less-than guard. Cells can be revisited multiple times; only commit the update when you strictly improve.

---

Complexity Analysis

	Time	Space
Dijkstra with heap	O(mn log mn)	O(mn)
0/1 Deque BFS	O(mn)	O(mn)

Bottleneck: Each cell enters the deque at most twice (once as 0-cost, once as 1-cost), giving linear work.

---

Edge Cases

1. Already-valid path of arrows — Cost 0.
2. All arrows point "up" — Need to flip a lot; answer approaches m + n - 2.
3. 1x1 grid — Answer 0 (start == end).
4. Single row with all arrows pointing right — Answer 0 if end is to the right; otherwise, flips needed.
5. Arrow cycle — Following arrows might loop forever. 0/1 BFS still terminates because dist only strictly decreases.

---

Related Problems

• LC 1368 — Minimum Cost to Make at Least One Valid Path in a Grid: Essentially identical.
• LC 2290 — Min Obstacle Removal: Same 0/1 Dijkstra technique, different weight meaning.
• LC 743 — Network Delay Time: General Dijkstra.
• LC 1514 — Path with Maximum Probability: Log-transformed Dijkstra.

---

What Is Expected at Each Level?

Junior / New Grad: Recognize shortest path and apply Dijkstra with a heap. May need a nudge to see the 0/1 deque trick.

Mid-level: Identify binary weights, write the deque solution, and justify the O(mn) bound.

Senior: Contrast both variants with timing, discuss when heap-Dijkstra is unavoidable (non-binary weights), extend to "K flips allowed" (augment state), and propose the union-find offline approach (process all 0-cost components first, then increment).