MediumNo. 0909
Snakes and Ladders — LeetCode 909 Python Solution
- Pattern
- Matrix and Grid
- Topics
- Breadth-First Search, Array, Matrix
- On a study list
- Top Interview 150
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.
Example
- Input
- board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
- Output
- 4
- Explanation
- In the beginning, you start at square 1 (at row 5, column 0).
Python solution
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
q = deque([1])
vis = {1}
ans = 0
m = n * n
while q:
for _ in range(len(q)):
x = q.popleft()
if x == m:
return ans
for y in range(x + 1, min(x + 6, m) + 1):
i, j = divmod(y - 1, n)
if i & 1:
j = n - j - 1
i = n - i - 1
z = y if board[i][j] == -1 else board[i][j]
if z not in vis:
vis.add(z)
q.append(z)
ans += 1
return -1Complexity
- Time
- O(n2)
- Space · auxiliary
- O(n2)
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 909. Snakes and Ladders 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 |
|---|---|---|
| 0864 | Shortest Path to Get All Keys | Hard |
| 0994 | Rotting Oranges | Medium |
| 1091 | Shortest Path in Binary Matrix | Medium |
| 1210 | Minimum Moves to Reach Target with Rotations | Hard |
| 1293 | Shortest Path in a Grid with Obstacles Elimination | Hard |
| 1765 | Map of Highest Peak | Medium |
Frequently asked questions
- How hard is LeetCode 909. Snakes and Ladders?
LeetCode 909. Snakes and Ladders is rated Medium on LeetCode.
- What is the time complexity of LeetCode 909. Snakes and Ladders?
The Python solution on this page runs in O(n2).
- What is the space complexity of LeetCode 909. Snakes and Ladders?
The Python solution on this page uses O(n2) auxiliary space.
- What topics does LeetCode 909. Snakes and Ladders cover?
LeetCode 909. Snakes and Ladders is tagged Breadth-First Search, Array and Matrix on LeetCode.