LeetCode 909: Snakes and Ladders — Python Solution

LeetCode 909: Snakes and Ladders is a Medium graph bfs problem. This Python walkthrough develops a board-index BFS solution, ties every code decision to a concrete invariant, and includes the regression check used before publication.

This independent guide paraphrases the task rather than reproducing LeetCode’s prompt. Use the official page for the exact statement, examples, constraints, and submission runner.

Recognizing the pattern

BFS explores an unweighted state graph in increasing move count, so the first arrival gives a shortest transformation.

For this problem specifically, map square numbers to boustrophedon coordinates and BFS over dice results, applying at most one snake or ladder per move. The invariant worth writing beside the code is: The first time BFS reaches a square uses the minimum number of dice throws.

Step-by-step algorithm

1. Identify the input state consumed by snakesAndLadders(board) and initialize the data required by the board-index BFS pattern.
2. Map square numbers to boustrophedon coordinates and BFS over dice results, applying at most one snake or ladder per move.
3. After each update, verify the page’s central invariant: The first time BFS reaches a square uses the minimum number of dice throws.
4. Finish only after the boundary behavior is covered: Do not chain a second jump in the same move; row direction alternates from the bottom.

Python solution

from collections import deque

class Solution:
    def snakesAndLadders(self, board):
        n = len(board)
        def coordinates(square):
            row_from_bottom, offset = divmod(square - 1, n)
            row = n - 1 - row_from_bottom
            col = offset if row_from_bottom % 2 == 0 else n - 1 - offset
            return row, col
        queue, seen = deque([(1, 0)]), {1}
        while queue:
            square, moves = queue.popleft()
            if square == n * n: return moves
            for rolled in range(square + 1, min(square + 6, n * n) + 1):
                r, c = coordinates(rolled)
                destination = board[r][c] if board[r][c] != -1 else rolled
                if destination not in seen:
                    seen.add(destination); queue.append((destination, moves + 1))
        return -1

Reading the implementation

The main entry point is snakesAndLadders(board). The named working state includes n, row_from_bottom, row, col, queue, square; those variables make the board-index BFS state visible instead of hiding it in incidental control flow.

The implementation uses 2 loops with separate responsibilities, so preprocessing and the main traversal can each stay linear in their own input. Early returns stop as soon as the answer is forced, avoiding work that cannot change the result. In concrete terms, map square numbers to boustrophedon coordinates and BFS over dice results, applying at most one snake or ladder per move.

Correctness argument

Initialization. The starting state is the only item in the first frontier, so its distance or level is exact.

Preservation. Map square numbers to boustrophedon coordinates and BFS over dice results, applying at most one snake or ladder per move. Because the queue processes earlier layers first, the first time BFS reaches a square uses the minimum number of dice throws.

Termination. Each state is accepted at most once. The first accepted goal therefore has the minimum possible layer, or exhausting the queue proves no valid path exists.

Complexity and trade-offs

O(n^2) time and O(n^2) space. The auxiliary-space figure excludes the returned output unless the output itself is the structure being built.

DFS can determine reachability but cannot stop at the first found path when a minimum number of moves is required. That comparison is useful in an interview because it explains why the final implementation is preferable, not merely that it passes.

Regression check

The published implementation belongs to a 100-problem suite that is compiled and exercised behaviorally before deployment.

One reference assertion from that suite is shown below. It targets the normal path while the edge conditions in the next section cover the failure-prone boundaries.

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]]; assert Solution().snakesAndLadders(board)==4

Common mistakes and edge cases

• Problem-specific boundary: Do not chain a second jump in the same move; row direction alternates from the bottom.
• Pattern-level pitfall: Generate only legal neighbors, mark them before enqueueing, and count layers consistently with the problem’s definition of a move.
• Invariant check: after every update, confirm that the first time BFS reaches a square uses the minimum number of dice throws.

Interview review checklist

• Explain why board-index BFS matches the structure of this input.
• State the invariant in one sentence before tracing code: The first time BFS reaches a square uses the minimum number of dice throws.
• Derive O(n^2) time and O(n^2) space from how many times each element or state is visited.
• Test the boundary explicitly: Do not chain a second jump in the same move; row direction alternates from the bottom.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 210. Course Schedule II · Next: 433. Minimum Genetic Mutation