We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Snakes and Ladders

Number: 945

Difficulty: Medium

Paid? No

Companies: Amazon, Goldman Sachs, TikTok, Apple, Anduril, Cisco, Microsoft, National Instruments, Bloomberg, Google

Problem Description

You are given an n x n board where each cell contains either -1 or a destination number indicating a snake or ladder. The board cells are labeled from 1 to n² in a boustrophedon (alternating) manner starting from the bottom-left corner. From a current square, you roll a standard six-sided die, moving between 1 and 6 steps ahead. If you land on a cell with a snake or ladder (i.e. its value is not -1), you must take it, which may immediately change your position. Your goal is to determine the minimum number of dice rolls required to reach square n²; if it is impossible to reach, return -1.

Key Insights

  • Use Breadth-First Search (BFS) to explore all possible moves from the start while tracking the number of dice rolls.
  • Convert the one-dimensional square number into board coordinates accounting for the alternating direction in each row.
  • When landing on a snake or ladder, follow it immediately, but only take one jump per roll.
  • Maintain a visited set or array to avoid re-processing cells and prevent infinite loops.

Space and Time Complexity

Time Complexity: O(n²) – each of the n² cells is processed at most once during the BFS. Space Complexity: O(n²) – used for the queue and visited set to store positions.

Solution

The problem is solved via a Breadth-First Search (BFS) approach. Starting from square 1, we explore all reachable squares (up to six moves ahead) for each dice roll. For each move, we convert the square number into board coordinates while considering the alternating order of rows. When a move encounters a snake or ladder (board value not equal to -1), we move directly to its destination. By using BFS, we ensure that the first time we reach the final square (n²) it is with the fewest moves possible. To guarantee no repeated work, we track visited squares.

Code Solutions

from collections import deque

def snakesAndLadders(board):
    n = len(board)
    
    # Helper function to convert a square number to board coordinates
    def get_position(square):
        # Determine row index from bottom to top
        quot, rem = divmod(square - 1, n)
        row = n - 1 - quot
        # For even rows (from bottom), direction is left->right; for odd rows, right->left.
        if quot % 2 == 0:
            col = rem
        else:
            col = n - 1 - rem
        return row, col
    
    visited = set()
    queue = deque([(1, 0)])  # tuple: (current square, moves)
    visited.add(1)
    
    while queue:
        curr, moves = queue.popleft()
        if curr == n * n:
            return moves
        for i in range(1, 7):  # simulate die roll
            next_sq = curr + i
            if next_sq > n * n:
                continue
            r, c = get_position(next_sq)
            # if there's a snake or ladder, take the jump
            if board[r][c] != -1:
                next_sq = board[r][c]
            if next_sq not in visited:
                visited.add(next_sq)
                queue.append((next_sq, moves + 1))
    return -1

# Example usage:
#print(snakesAndLadders([[-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]]))
← Back to All Questions