Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

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

My accepted Python solution to LeetCode problem 1485, Minimum Cost to Make at Least One Valid Path in a Grid, running in 90ms.

  • Difficulty: Hard
  • Python
  • Runtime 90ms
  • Memory 18.5MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 90ms, memory 18.5MB, accepted 2025-12-29.

python
class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        from collections import deque
        
        m, n = len(grid), len(grid[0])
        # Directions: 1=right, 2=left, 3=down, 4=up
        dirs = {1: (0, 1), 2: (0, -1), 3: (1, 0), 4: (-1, 0)}
        
        # 0-1 BFS using deque
        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = 0
        dq = deque([(0, 0)])
        
        while dq:
            i, j = dq.popleft()
            
            for d, (di, dj) in dirs.items():
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n:
                    # Cost is 0 if arrow points this direction, else 1
                    cost = 0 if grid[i][j] == d else 1
                    if dist[i][j] + cost < dist[ni][nj]:
                        dist[ni][nj] = dist[i][j] + cost
                        if cost == 0:
                            dq.appendleft((ni, nj))
                        else:
                            dq.append((ni, nj))
        
        return dist[m-1][n-1]

Source