#1368

Hard

auto_awesomeGraph traversal with breadth-first search

LeetCode Problem Workspace

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

Determine the minimum cost to create at least one valid path from the top-left to bottom-right in a directional grid.

array breadth first search graph heap priority queue matrix

Problem Statement

You are given an m x n grid where each cell contains a direction indicating which neighbor to visit next. Each arrow is represented by 1 (right), 2 (left), 3 (down), or 4 (up). Some arrows may point outside the grid. Starting at the top-left cell (0, 0), a valid path is any sequence of moves following the arrows that reaches the bottom-right cell (m - 1, n - 1).

You may modify the arrows in cells at a cost of 1 per change. The goal is to determine the minimum total cost required to ensure at least one valid path exists from the start to the destination. Follow the directional pattern strictly, accounting for cells that may initially misalign and require adjustments.

Examples

Example 1

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]

Output: 3

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

You can follow the path from (0, 0) to (2, 2).

Example 3

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

Output: 1

Example details omitted.

Constraints

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

Solution Approach

Model the Grid as a Weighted Graph

Convert each cell into a node connected to up to four neighbors. The edge weight is 0 if the cell's arrow points correctly toward the neighbor and 1 if the arrow must be changed. This sets up a graph traversal problem suitable for BFS or Dijkstra.

Use BFS or Priority Queue Traversal

Apply BFS with a deque or a priority queue to explore nodes while tracking cumulative cost. Cells reached following the arrow direction propagate with no additional cost, while changes increment the path cost. This ensures all feasible paths are explored efficiently.

Propagate Minimum Costs to Destination

Update each cell with the minimum cost found to reach it from the start. Continue traversal until reaching the bottom-right cell. The recorded cost at this cell represents the minimum total modifications required to guarantee a valid path.

Complexity Analysis

Metric	Value
Time	O(n \cdot m)
Space	O(n \cdot m)

Time complexity is O(m \cdot n) because each cell is visited at most once in BFS or Dijkstra traversal. Space complexity is O(m \cdot n) to store visited states and cumulative cost for each cell in the grid.

What Interviewers Usually Probe

Recognize the problem as a shortest path on a weighted grid using BFS.
Consider edge cases where arrows point outside the grid or initial path is already valid.
Be prepared to justify why 0-1 BFS or priority queue yields minimum modification cost.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly assign zero cost to moves following the existing arrow direction.
Overlooking cells with arrows pointing outside the grid, leading to invalid path assumptions.
Using standard BFS without handling edge weights, which undercounts modification costs.

Follow-up variants

Find the maximum number of valid paths from start to end instead of minimum cost.
Allow diagonal movements with corresponding arrow adjustments and costs.
Compute minimum cost if multiple start points are allowed in the top row or left column.

FAQ

What does 'minimum cost to make at least one valid path in a grid' mean?

It means calculating the smallest number of arrow changes needed so that a path exists from the top-left to bottom-right following the directional rules.

Which algorithm pattern best solves this problem?

This problem is best solved using a graph traversal pattern, specifically 0-1 BFS or Dijkstra, to track minimal modification costs.

Can the initial grid already have a valid path?

Yes, if following the existing arrows from start to finish reaches the bottom-right cell, the minimum cost is zero.

How do I handle arrows pointing outside the grid?

Treat moves pointing outside the grid as invalid. These cells must be changed or avoided in the BFS traversal to reach the destination.

Is this approach efficient for large grids?

Yes, the BFS-based or priority queue traversal runs in O(m \cdot n) time and space, handling grids up to 100x100 efficiently.

terminal

Solution

Solution 1: Double-ended Queue BFS

This problem is essentially a shortest path model, but what we are looking for is the minimum number of direction changes.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dirs = [[0, 0], [0, 1], [0, -1], [1, 0], [-1, 0]]
        q = deque([(0, 0, 0)])
        vis = set()
        while q:
            i, j, d = q.popleft()
            if (i, j) in vis:
                continue
            vis.add((i, j))
            if i == m - 1 and j == n - 1:
                return d
            for k in range(1, 5):
                x, y = i + dirs[k][0], j + dirs[k][1]
                if 0 <= x < m and 0 <= y < n:
                    if grid[i][j] == k:
                        q.appendleft((x, y, d))
                    else:
                        q.append((x, y, d + 1))
        return -1

Continue Practicing

#1631 path with minimum effort #787 cheapest flights within k stops #778 swim in rising water