Minimum Cost to Make at Least One Valid Path in a Grid: 0-1 BFS Pattern

You are given an m x n grid where each cell has a sign pointing in one of four directions: right (1), left (2), down (3), or up (4). You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m-1, n-1). You can follow the sign in any cell for free, or you can change a cell's sign to any other direction at a cost of 1. Find the minimum total cost to create a valid path from (0, 0) to (m-1, n-1).

This is LeetCode 1368: Minimum Cost to Make at Least One Valid Path in a Grid, and it is one of the cleanest examples of 0-1 BFS. The technique it teaches applies to any shortest-path problem where edge weights are restricted to 0 and 1.

Why this problem matters

Most shortest-path problems hand you a graph with arbitrary non-negative weights and point you toward Dijkstra's algorithm. That works, but Dijkstra uses a priority queue with O(log n) insertions and extractions. When every edge weight is either 0 or 1, you can do better. A deque (double-ended queue) replaces the priority queue, and every insertion becomes O(1). The resulting algorithm is called 0-1 BFS.

This matters because 0-1 BFS shows up in disguise across many grid problems. Any time you are on a grid and can move in one direction for free but pay a cost to move in another, you are looking at a 0-1 weighted graph. Problems like "Shortest Path in a Grid with Obstacles Elimination," "Minimum Cost to Move Chips," and maze problems with free corridors and paid walls all follow the same template.

Understanding 0-1 BFS also deepens your grasp of why BFS works for unweighted graphs in the first place. Regular BFS is really just 0-0 BFS: every edge has weight 0 (or equivalently, weight 1 with level-by-level processing). When you add weight-1 edges alongside weight-0 edges, the deque trick preserves the "closest first" property that makes BFS correct, without the overhead of a heap.

The key insight

Model the grid as a graph. Each cell is a node. From every cell, you have four possible moves (up, down, left, right). If the move follows the cell's current sign, the edge weight is 0. If it requires changing the sign, the edge weight is 1. Now you need the shortest path from (0, 0) to (m-1, n-1) in a graph where all edges are 0 or 1.

Use a deque instead of a priority queue. When you explore a neighbor with cost 0 (following the sign), push it to the front of the deque. When you explore a neighbor with cost 1 (changing the sign), push it to the back. This ensures you always process the lowest-cost cell next, just like Dijkstra, but in O(1) per operation instead of O(log n).

The algorithm:

1. Initialize a distance array with infinity everywhere except dist[0][0] = 0.
2. Push (0, 0) onto the deque.
3. Pop from the front. For each of the four neighbors, compute the edge weight: 0 if the current cell's sign points to that neighbor, 1 otherwise.
4. If dist[current] + weight is less than dist[neighbor], update and push. Weight 0 goes to the front, weight 1 goes to the back.
5. When you pop (m-1, n-1), return its distance.

The solution

from collections import deque

def min_cost(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    # direction mappings: 1=right, 2=left, 3=down, 4=up
    dirs = {1: (0, 1), 2: (0, -1), 3: (1, 0), 4: (-1, 0)}
    all_moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    dist = [[float("inf")] * n for _ in range(m)]
    dist[0][0] = 0
    dq = deque([(0, 0)])

    while dq:
        r, c = dq.popleft()
        for dr, dc in all_moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                # cost is 0 if the sign already points this way
                cost = 0 if dirs[grid[r][c]] == (dr, dc) else 1
                if dist[r][c] + cost < dist[nr][nc]:
                    dist[nr][nc] = dist[r][c] + cost
                    if cost == 0:
                        dq.appendleft((nr, nc))
                    else:
                        dq.append((nr, nc))

    return dist[m - 1][n - 1]

Let's walk through what each piece does.

The dirs dictionary maps each sign value to the row and column offset it represents. This lets us check whether a cell's sign already points toward a given neighbor. If it does, the cost is 0. Otherwise, we would need to change the sign, so the cost is 1.

The distance array dist tracks the cheapest known cost to reach each cell. We initialize everything to infinity and set the start cell to 0. This mirrors the setup in Dijkstra's algorithm.

The core loop pops from the front of the deque. For each of the four neighbors, we compute the edge weight and check if we found a cheaper path. If we did, we update the distance and push the neighbor. The key detail: cost-0 neighbors go to the front of the deque (they are as close as the current cell), while cost-1 neighbors go to the back (they are one step farther). This preserves the invariant that we always process the cheapest reachable cell next.

Visual walkthrough

Let's trace through the example grid step by step. Watch how 0-1 BFS explores all cost-0 cells first (pushing to the front) before processing cost-1 cells (pulled from the back).

Notice that the deque naturally separates the exploration into "waves." All cells reachable at cost 0 get processed before any cell at cost 1. Within the cost-1 wave, cells reachable at cost 1 are processed before cost 2. This is the same level-by-level property as regular BFS, extended to handle two weights.

Complexity analysis

Time is O(m * n). Each cell is pushed onto the deque at most a constant number of times (once from a cost-0 edge, once from a cost-1 edge). Each pop and each neighbor check is O(1). Total work is proportional to the number of cells.

Space is O(m * n) for the distance array and the deque. In the worst case, the deque holds all cells.

The building blocks

1. 0-1 BFS with deque

The core pattern: use appendleft for weight-0 edges and append for weight-1 edges.

dq = deque([start])
dist[start] = 0

while dq:
    node = dq.popleft()
    for neighbor, weight in edges(node):
        if dist[node] + weight < dist[neighbor]:
            dist[neighbor] = dist[node] + weight
            if weight == 0:
                dq.appendleft(neighbor)
            else:
                dq.append(neighbor)

This is the template you will reuse whenever edge weights are 0 or 1. It replaces Dijkstra's heap with a deque and drops the time complexity from O(E log V) to O(V + E). You will see this in "Minimum Cost to Move Chips," "Shortest Path in a Grid with Obstacles," and any problem where one action is free and another costs a fixed amount.

2. Grid direction mapping

Translating cell values into movement offsets:

dirs = {1: (0, 1), 2: (0, -1), 3: (1, 0), 4: (-1, 0)}
cost = 0 if dirs[grid[r][c]] == (dr, dc) else 1

This converts the problem's encoding into something you can compute with. The sign in each cell determines which of the four edges leaving that cell has weight 0. The other three edges have weight 1. This mapping pattern shows up in any grid problem where cells encode a preferred direction.

Edge cases

Before submitting, think through these scenarios:

• 1x1 grid: The start is the destination. Return 0 immediately.
• Already valid path: All signs lead from (0,0) to (m-1,n-1) without any changes. Cost is 0.
• Single row: You just need to move right across the row. Cost equals the number of cells not pointing right.
• Single column: You just need to move down. Cost equals the number of cells not pointing down.
• All signs point left or up: Every move toward the goal costs 1. The answer equals the Manhattan distance (m - 1) + (n - 1).
• Large grid with all signs correct: 0-1 BFS still runs in O(m * n), just with all edges at weight 0.

From understanding to recall

You have seen how 0-1 BFS works: model the grid as a weighted graph with 0 and 1 edges, use a deque to process cheapest-first, and track distances in a 2D array. The code is concise and the logic is clean. But recognizing when to apply 0-1 BFS during an interview is the real challenge.

The trigger to look for: a shortest-path problem where you can classify every action as either "free" or "costs one unit." The moment you see that binary distinction in edge weights, skip the priority queue and use a deque. This is faster to code, faster to run, and easier to get right under pressure.

Spaced repetition helps you internalize this recognition. You practice the deque template, the direction mapping, and the front-vs-back push logic from memory at increasing intervals. After a few sessions, the pattern becomes reflexive. You see "move for free or pay to change direction" and the 0-1 BFS template writes itself.

Related posts

• Rotting Oranges - Multi-source BFS on a grid
• Shortest Path in Binary Matrix - BFS shortest path on grid
• Shortest Bridge - Multi-source BFS between islands

CodeBricks breaks this problem into its 0-1 BFS deque pattern and grid direction mapping building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a weighted grid problem shows up in your interview, you do not think about it. You just write it.