Leetcode #909: Snakes and Ladders
In this guide, we solve Leetcode #909 Snakes and Ladders in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Breadth-First Search, Array, Matrix
Intuition
We need level-by-level exploration or shortest steps, which is ideal for BFS.
A queue naturally models the frontier of the search.
Approach
Push initial nodes into a queue and expand in layers.
Track visited nodes to prevent cycles.
Steps:
- Initialize queue with start nodes.
- Process level by level.
- Track visited nodes.
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).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.
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 -1
Complexity
The time complexity is , and the space complexity is . The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.