We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 1485

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an m x n grid where each cell contains a direction (1: right, 2: left, 3: down, 4: up), we must start from the top-left cell (0,0) and follow the arrows to potentially reach the bottom-right cell (m-1, n-1). We are allowed to change the direction in any cell at a cost of 1 (each cell’s direction can be changed only once). The objective is to determine the minimum total cost required to have at least one valid path from the start to the destination.

Key Insights

  • The problem can be viewed as finding the shortest path in a grid where moving in the designated arrow direction costs 0 and any change (i.e., moving in any other direction) costs 1.
  • This is a weighted graph problem with two edge costs: 0 and 1, making it a natural candidate for a 0-1 Breadth First Search (BFS) algorithm.
  • With 0-1 BFS, we use a dequeue (double-ended queue) to efficiently process nodes ensuring that 0-cost moves are prioritized.
  • The grid dimensions are limited (m, n ≤ 100), so using a BFS-based algorithm leads to a manageable number of states.

Space and Time Complexity

Time Complexity: O(m * n) – Each cell is processed, and there can be at most a constant number of operations per cell with 0-1 BFS. Space Complexity: O(m * n) – The auxiliary space for the cost matrix and the dequeue is proportional to the number of grid cells.

Solution

We use a 0-1 BFS approach to solve the problem. We view each cell as a node in a graph. For a given cell (i, j):

  • Moving in the direction indicated by the cell is free (cost 0).
  • Moving in any other direction requires modifying the cell’s direction (cost 1). A deque is used to store the cells to be processed. When a move has 0 cost, we add that cell to the front of the deque so that it is processed sooner; moves with cost 1 are added to the back. This guarantees that we always expand the current least-cost path. We maintain a cost matrix to keep track of the minimum cost achieved to reach each cell, stopping when the target cell (m-1, n-1) is reached.

Code Solutions

from collections import deque

def minCost(grid):
    m, n = len(grid), len(grid[0])
    # Directions: right, left, down, up correspond to 0,1,2,3 in our 0-indexed list.
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    # cost matrix initialized with infinity
    cost = [[float('inf')] * n for _ in range(m)]
    cost[0][0] = 0
    dq = deque()
    dq.append((0, 0))
    
    while dq:
        i, j = dq.popleft()
        # If reached the destination, return the cost immediately.
        if i == m - 1 and j == n - 1:
            return cost[i][j]
        for k, (di, dj) in enumerate(directions):
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n:
                # If the current direction (grid[i][j]) matches the direction index k+1 then costChange is 0; otherwise 1.
                cost_change = 0 if grid[i][j] == k + 1 else 1
                if cost[i][j] + cost_change < cost[ni][nj]:
                    cost[ni][nj] = cost[i][j] + cost_change
                    if cost_change == 0:
                        dq.appendleft((ni, nj))
                    else:
                        dq.append((ni, nj))
    return cost[m-1][n-1]

# Example usage:
grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
print(minCost(grid))
← Back to All Questions