909. Snakes And Ladders - Explanation

1. Breadth First Search - I

Intuition

This is a shortest path problem on an implicit graph where each square connects to the next 1 to 6 squares (simulating a dice roll). BFS naturally finds the shortest path in an unweighted graph. The tricky part is converting between square numbers and board coordinates, since the board uses a boustrophedon (zigzag) pattern starting from the bottom-left.

Algorithm

Create a helper function to convert a square number to board coordinates, accounting for the alternating row directions.
Initialize a queue with square 1 and 0 moves, along with a visited set.
While the queue is not empty:
- Dequeue the current square and move count.
- For each dice roll (1 to 6), calculate the next square.
- Convert to board coordinates and check for snakes/ladders (non -1 values).
- If the destination is the final square, return moves + 1.
- If not visited, mark as visited and enqueue with incremented move count.
Return -1 if the final square is unreachable.

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)

        def intToPos(square):
            r = (square - 1) // n
            c = (square - 1) % n
            if r % 2 == 1:
                c = n - 1 - c
            r = n - 1 - r
            return r, c

        q = deque([(1, 0)])
        visit = set()

        while q:
            square, moves = q.popleft()

            for i in range(1, 7):
                nextSquare = square + i
                r, c = intToPos(nextSquare)
                if board[r][c] != -1:
                    nextSquare = board[r][c]

                if nextSquare == n * n:
                    return moves + 1

                if nextSquare not in visit:
                    visit.add(nextSquare)
                    q.append((nextSquare, moves + 1))

        return -1

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

2. Breadth First Search - II

Intuition

This variation uses a distance array instead of a visited set, storing the minimum moves to reach each square. This approach is slightly more explicit about tracking distances and allows for early termination once we reach the destination. The core BFS logic remains the same.

Algorithm

Initialize a distance array with -1 for all squares except square 1 (set to 0).
Start bfs from square 1.
For each square processed:
- Try all dice rolls (1 to 6).
- Skip if the next square exceeds the board.
- Apply any snake or ladder at the landing position.
- If this square has not been visited (distance is -1), set its distance and check if it is the destination.
- Enqueue the square for further exploration.
Return the distance to the final square, or -1 if unreachable.

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)

        def intToPos(square):
            r = (square - 1) // n
            c = (square - 1) % n
            if r % 2 == 1:
                c = n - 1 - c
            r = n - 1 - r
            return r, c

        dist = [-1] * (n * n + 1)
        q = deque([1])
        dist[1] = 0

        while q:
            square = q.popleft()

            for i in range(1, 7):
                nextSquare = square + i
                if nextSquare > n * n:
                    break

                r, c = intToPos(nextSquare)
                if board[r][c] != -1:
                    nextSquare = board[r][c]

                if dist[nextSquare] == -1:
                    dist[nextSquare] = dist[square] + 1
                    if nextSquare == n * n:
                        return dist[nextSquare]
                    q.append(nextSquare)

        return -1

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Breadth First Search - III

Intuition

This optimization modifies the board in place to track visited squares, eliminating the need for a separate visited set or distance array. By marking visited positions directly on the board with a special value (0), we reduce memory overhead while maintaining the same BFS traversal logic.

Algorithm

Initialize a queue with square 1 and mark the starting position on the board as visited (set to 0).
Process the queue level by level, tracking the current move count.
For each square in the current level:
- Try all dice rolls (1 to 6).
- Skip if the next square exceeds the board.
- Apply any snake or ladder at the landing position.
- If the board position is not marked as visited (not 0), check for destination and enqueue.
- Mark the position as visited by setting it to 0.
Increment moves after processing each level and return -1 if unreachable.

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)

        def intToPos(square):
            r = (square - 1) // n
            c = (square - 1) % n
            if r % 2 == 1:
                c = n - 1 - c
            r = n - 1 - r
            return r, c

        q = deque([1])
        board[n - 1][0] = 0
        moves = 0

        while q:
            for _ in range(len(q)):
                square = q.popleft()

                for i in range(1, 7):
                    nextSquare = square + i
                    if nextSquare > n * n:
                        break

                    r, c = intToPos(nextSquare)
                    if board[r][c] != -1:
                        nextSquare = board[r][c]

                    if board[r][c] != 0:
                        if nextSquare == n * n:
                            return moves + 1
                        q.append(nextSquare)
                        board[r][c] = 0
            moves += 1

        return -1

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

Common Pitfalls

Incorrect Square-to-Coordinate Conversion

The board uses a boustrophedon (zigzag) pattern starting from the bottom-left, with alternating row directions. A common mistake is not flipping the column index for odd rows or forgetting that row 0 in the board array corresponds to the top of the visual board. Always verify your conversion function with examples from different rows.

Marking the Wrong Square as Visited

After taking a snake or ladder, you land on a different square than where you initially rolled to. The visited check should be based on the final destination after any snake/ladder, but the board position to check for snakes/ladders is the intermediate square. Confusing these leads to revisiting squares or missing valid paths.

Not Handling Squares Beyond the Board

When rolling dice from a square close to the end, some rolls may exceed n * n. These rolls are invalid and should be skipped, not treated as reaching the destination. Always check nextSquare > n * n before processing a dice roll.