MediumNo. 0490LeetCode Premium
The Maze — LeetCode 490 Python Solution
- Pattern
- Matrix and Grid
- Topics
- Depth-First Search, Breadth-First Search, Array, Matrix
- Reading time
- 4 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,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
- Output
- true
- Explanation
- One possible way is : left -> down -> left -> down -> right -> down -> right.
Python solution
class Solution:
def hasPath(
self, maze: List[List[int]], start: List[int], destination: List[int]
) -> bool:
def dfs(i, j):
if vis[i][j]:
return
vis[i][j] = True
if [i, j] == destination:
return
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
x, y = i, j
while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0:
x, y = x + a, y + b
dfs(x, y)
m, n = len(maze), len(maze[0])
vis = [[False] * n for _ in range(m)]
dfs(start[0], start[1])
return vis[destination[0]][destination[1]]Complexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 490. The Maze is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0130 | Surrounded Regions | Medium |
| 0200 | Number of Islands | Medium |
| 0417 | Pacific Atlantic Water Flow | Medium |
| 0463 | Island Perimeter | Easy |
| 0529 | Minesweeper | Medium |
| 0695 | Max Area of Island | Medium |
Frequently asked questions
- How hard is LeetCode 490. The Maze?
LeetCode 490. The Maze is rated Medium on LeetCode.
- What is the time complexity of LeetCode 490. The Maze?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 490. The Maze?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 490. The Maze cover?
LeetCode 490. The Maze is tagged Depth-First Search, Breadth-First Search, Array and Matrix on LeetCode.
- Is LeetCode 490. The Maze a premium problem?
Yes. LeetCode 490. The Maze is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.