What is the time complexity of LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid?

The Python solution on this page runs in O(n log n).

What is the space complexity of LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid?

The Python solution on this page uses O(n) auxiliary space.

Minimum Cost to Make at Least One Valid Path in a Grid — LeetCode 1368 Python Solution

HardBreadth-First SearchGraphArrayMatrixShortest PathHeap (Priority Queue)

Problem: #1368
Pattern: Heap / Priority Queue
Reading time: 4 min
Source: leetcode.com

The problem

Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell.

Example

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n log n)
Space	O(n) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid?: LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid is rated Hard on LeetCode.
What is the time complexity of LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid?: The Python solution on this page runs in O(n log n).
What is the space complexity of LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid cover?: LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid is tagged Breadth-First Search, Graph, Array, Matrix, Shortest Path and Heap (Priority Queue) on LeetCode.