How hard is LeetCode 499. The Maze III?

LeetCode 499. The Maze III is rated Hard on LeetCode.

What is the time complexity of LeetCode 499. The Maze III?

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

What is the space complexity of LeetCode 499. The Maze III?

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

Is LeetCode 499. The Maze III a premium problem?

Yes. LeetCode 499. The Maze III is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

The Maze III — LeetCode 499 Python Solution

HardLeetCode PremiumDepth-First SearchBreadth-First SearchGraphArrayStringMatrixShortest PathHeap (Priority Queue)

Problem: #499
Pattern: Heap / Priority Queue
Reading time: 6 min
Source: leetcode.com

The problem

There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall.

Example

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"
Explanation: There are two shortest ways for the ball to drop into the hole.

Python solution

Python

class Solution:
    def findShortestWay(
        self, maze: List[List[int]], ball: List[int], hole: List[int]
    ) -> str:
        m, n = len(maze), len(maze[0])
        r, c = ball
        rh, ch = hole
        q = deque([(r, c)])
        dist = [[inf] * n for _ in range(m)]
        dist[r][c] = 0
        path = [[None] * n for _ in range(m)]
        path[r][c] = ''
        while q:
            i, j = q.popleft()
            for a, b, d in [(-1, 0, 'u'), (1, 0, 'd'), (0, -1, 'l'), (0, 1, 'r')]:
                x, y, step = i, j, dist[i][j]
                while (
                    0 <= x + a < m
                    and 0 <= y + b < n
                    and maze[x + a][y + b] == 0
                    and (x != rh or y != ch)
                ):
                    x, y = x + a, y + b
                    step += 1
                if dist[x][y] > step or (
                    dist[x][y] == step and path[i][j] + d < path[x][y]
                ):
                    dist[x][y] = step
                    path[x][y] = path[i][j] + d
                    if x != rh or y != ch:
                        q.append((x, y))
        return path[rh][ch] or 'impossible'

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 499. The Maze III 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 499. The Maze III?: LeetCode 499. The Maze III is rated Hard on LeetCode.
What is the time complexity of LeetCode 499. The Maze III?: The Python solution on this page runs in O(n log n).
What is the space complexity of LeetCode 499. The Maze III?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 499. The Maze III cover?: LeetCode 499. The Maze III is tagged Depth-First Search, Breadth-First Search, Graph, Array, String, Matrix, Shortest Path and Heap (Priority Queue) on LeetCode.
Is LeetCode 499. The Maze III a premium problem?: Yes. LeetCode 499. The Maze III is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.