Snakes and Ladders

Med

#0863Time: O(6^D), where D is the length of the longest simple path. In the worst case, this is exponential in N^2, making it infeasible for all but the smallest boards.Space: O(N^2) for the recursion stack depth in the worst case, where N is the side length of the board. The `visitedOnPath` array also takes O(N^2) space.7 companies

Algorithms

Breadth-First Search

Data structures

Array Matrix

Companies

Cisco PhonePe Zomato Pinterest

Prompt

You are given an n x n integer matrix board where the cells are labeled from 1 to n² in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n²)].
- This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
The game ends when you reach the square n².

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n² are not the starting points of any snake or ladder.

Note that you only take a snake or ladder at most once per dice roll. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of dice rolls required to reach the square n². If it is not possible to reach the square, return -1.

Example 1:

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.

Example 2:

Input: board = [[-1,-1],[-1,3]]
Output: 1

Constraints:

n == board.length == board[i].length
2 <= n <= 20
board[i][j] is either -1 or in the range [1, n²].
The squares labeled 1 and n² are not the starting points of any snake or ladder.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach explores the game by trying every possible sequence of dice rolls recursively. It's a brute-force method that attempts to find a path to the destination square n*n. To find the shortest path, it must explore all possible paths from the start to the end and keep track of the minimum number of moves found so far. This is fundamentally inefficient because it doesn't prioritize shorter paths and explores many dead-ends and suboptimal routes.

Algorithm

Initialize a global variable min_moves to infinity.
Create a helper function getCoordinates(square) to convert a square number to its (row, col) coordinates.
Define a recursive function dfs(square, moves, visited_path).
Inside dfs:
- If the current number of moves is already greater than or equal to min_moves, we can prune this path and return, as it won't be a better solution.
- If square is the target n*n, we have found a path. We update min_moves = min(min_moves, moves) and return.
- Mark the current square as visited in the current path to avoid cycles within a single path exploration.
- Iterate through each possible dice roll d from 1 to 6:
  - Calculate next_square = square + d.
  - If next_square exceeds n*n, stop exploring further dice rolls from this square.
  - Use the helper function to get the coordinates for next_square.
  - Check the board for a snake or ladder to determine the final_dest.
  - If final_dest has not been visited in the current path, make a recursive call: dfs(final_dest, moves + 1, visited_path).
- Unmark square from visited_path to allow other paths to visit this square (this is called backtracking).
Start the search by calling dfs(1, 0, new HashSet<>()).
After the search completes, if min_moves is still infinity, it means the destination was unreachable, so return -1. Otherwise, return min_moves.

Walkthrough

We define a recursive function, say dfs(currentSquare, currentMoves), that explores paths from the currentSquare. The base case for the recursion is when currentSquare reaches n*n, at which point we compare currentMoves with a global minimum and update it if the current path is shorter. To prevent infinite loops (e.g., a snake leading back to a square we've already been on in the current path), we need to keep track of the squares visited along the current recursive path.

The function iterates through all possible next moves (dice rolls 1 to 6). For each move, it calculates the destination square, accounting for any snakes or ladders. It then makes a recursive call for the new square with an incremented move count. This approach is very inefficient because it explores paths in a depth-first manner, meaning it might explore a very long path completely before exploring a much shorter one. It essentially performs an exhaustive search of the state space, which is exponential in nature.

1class Solution {2    int minMoves = Integer.MAX_VALUE;3    int n;4 5    public int snakesAndLadders(int[][] board) {6        this.n = board.length;7        // Using a boolean array for the visited path for simplicity8        dfs(1, 0, new boolean[n * n + 1], board);9        return minMoves == Integer.MAX_VALUE ? -1 : minMoves;10    }11 12    private void dfs(int currentSquare, int moves, boolean[] visitedOnPath, int[][] board) {13        // Pruning: if we've already taken more moves than the best solution found so far14        if (moves >= minMoves) {15            return;16        }17 18        // Mark the current square as visited for this path19        visitedOnPath[currentSquare] = true;20 21        for (int i = 1; i <= 6; i++) {22            int nextSquare = currentSquare + i;23            if (nextSquare > n * n) {24                break;25            }26 27            int[] coords = getCoordinates(nextSquare);28            int r = coords[0];29            int c = coords[1];30 31            int finalDestination = board[r][c] == -1 ? nextSquare : board[r][c];32 33            if (finalDestination == n * n) {34                minMoves = Math.min(minMoves, moves + 1);35                // We can continue checking other dice rolls, as a shorter path might exist36                // from the current square, though this is unlikely with this problem's structure.37                continue;38            }39 40            if (!visitedOnPath[finalDestination]) {41                dfs(finalDestination, moves + 1, visitedOnPath, board);42            }43        }44        45        // Backtrack: un-mark the square so other paths can use it46        visitedOnPath[currentSquare] = false;47    }48 49    private int[] getCoordinates(int square) {50        int r = n - 1 - (square - 1) / n;51        int c = (square - 1) % n;52        if ((n - 1 - r) % 2 == 1) { // Odd row from top (0-indexed)53            c = n - 1 - c;54        }55        return new int[]{r, c};56    }57}

Complexity

Time

O(6^D), where D is the length of the longest simple path. In the worst case, this is exponential in N^2, making it infeasible for all but the smallest boards.

Space

O(N^2) for the recursion stack depth in the worst case, where N is the side length of the board. The `visitedOnPath` array also takes O(N^2) space.

Trade-offs

Pros

Conceptually simple to understand as it mimics trying out all possibilities.

Cons

Extremely inefficient and will likely result in a "Time Limit Exceeded" error for most inputs.
Does not find the shortest path first; it must explore a potentially large number of paths to guarantee the minimum.
The state space can be very large, leading to deep recursion and potential stack overflow errors on large boards.

This problem can be modeled as finding the shortest path in an unweighted graph. Each square on the board is a node, and a move (a dice roll followed by a potential snake or ladder) represents an edge. Breadth-First Search (BFS) is the ideal algorithm for this scenario because it explores the graph layer by layer. This guarantees that the first time we reach the destination square n*n, it will be via the path with the minimum number of moves.

Algorithm

Get the board size n.
Create a helper function getCoordinates(square, n) to convert a square number to its (row, col) coordinates.
Initialize a queue q of integers and add the starting square 1.
Initialize a boolean array visited of size n*n + 1 and set visited[1] = true to avoid cycles and redundant processing.
Initialize a variable moves = 0.
While the queue q is not empty:
- Get the number of nodes at the current level: levelSize = q.size().
- Loop levelSize times to process all nodes at the current level before moving to the next.
  - Dequeue the current square: curr = q.poll().
  - If curr is the target square n*n, we have found the shortest path. Return moves.
  - For each possible dice roll d from 1 to 6:
    - Calculate the potential next square: next = curr + d.
    - If next > n*n, break the inner loop as further rolls will also be out of bounds.
    - Get the board coordinates for next: (r, c) = getCoordinates(next, n).
    - Determine the final destination after checking for a snake or ladder: dest = board[r][c] == -1 ? next : board[r][c].
    - If dest has not been visited (visited[dest] is false):
      - Mark it as visited: visited[dest] = true.
      - Enqueue dest for processing in the next level: q.add(dest).
- After processing the entire level, increment moves.
If the loop finishes (queue becomes empty) and we haven't reached the destination, it's unreachable. Return -1.

Walkthrough

We start at square 1, which is at level 0 of our search. All squares reachable in one move are at level 1, all squares reachable from level 1 squares in one move are at level 2, and so on. BFS systematically explores these levels using a queue.

We use a queue to keep track of the squares to visit next and a visited array to ensure we don't process the same square multiple times, which prevents infinite loops and redundant computations. The search proceeds level by level. In each step, we dequeue all nodes from the current level, find all their unvisited neighbors (squares reachable in one move), and enqueue them. We increment our move counter after each level is fully processed. Because we explore all paths of length k before exploring any path of length k+1, the first time we encounter the target square, we are guaranteed to have done so in the minimum possible number of moves.

1import java.util.LinkedList;2import java.util.Queue;3 4class Solution {5    public int snakesAndLadders(int[][] board) {6        int n = board.length;7        boolean[] visited = new boolean[n * n + 1];8        Queue<Integer> queue = new LinkedList<>();9 10        queue.offer(1);11        visited[1] = true;12        int moves = 0;13 14        while (!queue.isEmpty()) {15            int levelSize = queue.size();16            for (int i = 0; i < levelSize; i++) {17                int currentSquare = queue.poll();18 19                if (currentSquare == n * n) {20                    return moves;21                }22 23                for (int j = 1; j <= 6; j++) {24                    int nextSquare = currentSquare + j;25                    if (nextSquare > n * n) {26                        break;27                    }28 29                    int[] coords = getCoordinates(nextSquare, n);30                    int r = coords[0];31                    int c = coords[1];32 33                    int finalDestination = board[r][c] == -1 ? nextSquare : board[r][c];34 35                    if (!visited[finalDestination]) {36                        visited[finalDestination] = true;37                        queue.offer(finalDestination);38                    }39                }40            }41            moves++;42        }43 44        return -1; // Destination not reachable45    }46 47    private int[] getCoordinates(int square, int n) {48        // Convert 1-based square to 0-based index for calculation49        int s = square - 1;50        51        // Row from top (0-indexed)52        int rowFromTop = s / n;53        // Board row (from bottom, 0-indexed)54        int r = n - 1 - rowFromTop;55 56        // Column (0-indexed)57        int c = s % n;58        // Adjust column for Boustrophedon order59        if (rowFromTop % 2 == 1) { // If row from top is odd, direction is right-to-left60            c = n - 1 - c;61        }62        63        return new int[]{r, c};64    }65}

Complexity

Time

O(N^2), where N is the side length of the board. Each square (node) from 1 to N^2 is enqueued and dequeued at most once. From each square, we perform a constant number of operations (at most 6) to find its neighbors. Therefore, the complexity is proportional to the number of squares.

Space

O(N^2), where N is the side length of the board. The `visited` array requires O(N^2) space. The queue, in the worst case, can also hold up to O(N^2) elements.

Trade-offs

Pros

Guaranteed to find the shortest path in terms of the number of moves for an unweighted graph.
Highly efficient and the optimal approach for this problem.
Cleanly avoids infinite cycles and redundant computations using a visited set.

Cons

Requires extra space for the queue and the visited array, which can be up to O(N^2).

Solutions

Solution

1class Solution {2private3  int n;4public5  int snakesAndLadders(int[][] board) {6    n = board.length;7    Deque<Integer> q = new ArrayDeque<>();8    q.offer(1);9    boolean[] vis = new boolean[n * n + 1];10    vis[1] = true;11    int ans = 0;12    while (!q.isEmpty()) {13      for (int t = q.size(); t > 0; --t) {14        int curr = q.poll();15        if (curr == n * n) {16          return ans;17        }18        for (int k = curr + 1; k <= Math.min(curr + 6, n * n); ++k) {19          int[] p = get(k);20          int next = k;21          int i = p[0], j = p[1];22          if (board[i][j] != -1) {23            next = board[i][j];24          }25          if (!vis[next]) {26            vis[next] = true;27            q.offer(next);28          }29        }30      }31      ++ans;32    }33    return -1;34  }35private36  int[] get(int x) {37    int i = (x - 1) / n, j = (x - 1) % n;38    if (i % 2 == 1) {39      j = n - 1 - j;40    }41    return new int[]{n - 1 - i, j};42  }43}

1class Solution {2public:3  int n;4  int snakesAndLadders(vector<vector<int>> &board) {5    n = board.size();6    queue<int> q{{1}};7    vector<bool> vis(n * n + 1);8    vis[1] = true;9    int ans = 0;10    while (!q.empty()) {11      for (int t = q.size(); t; --t) {12        int curr = q.front();13        if (curr == n * n)14          return ans;15        q.pop();16        for (int k = curr + 1; k <= min(curr + 6, n * n); ++k) {17          auto p = get(k);18          int next = k;19          int i = p[0], j = p[1];20          if (board[i][j] != -1)21            next = board[i][j];22          if (!vis[next]) {23            vis[next] = true;24            q.push(next);25          }26        }27      }28      ++ans;29    }30    return -1;31  }32  vector<int> get(int x) {33    int i = (x - 1) / n, j = (x - 1) % n;34    if (i % 2 == 1)35      j = n - 1 - j;36    return {n - 1 - i, j};37  }38};

1class Solution:2    def snakesAndLadders(self, board: List[List[int]]) -> int: def get(x): i, j = (x - 1) // n, (x - 1) % n if i & 1: j = n - 1 - j return n - 1 - i, j n = len(board) q = deque([1]) vis = {1} ans = 0 while q: for _ in range(len(q)): curr = q . popleft() if curr == n * n: return ans for next in range(curr + 1, min(curr + 7, n * n + 1)): i, j = get(next) if board[i][j] != - 1: next = board[i][j] if next not in vis: q . append(next) vis . add(next) ans += 1 return - 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem