Watch 10 video solutions for Snakes and Ladders, a medium level problem involving Array, Breadth-First Search, Matrix. This walkthrough by NeetCode has 75,323 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
You start on square 1 of the board. In each move, starting from square curr, do the following:
next with a label in the range [curr + 1, min(curr + 6, n2)].
next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.n2.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 n2 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.
[[-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 n2. 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].length2 <= n <= 20board[i][j] is either -1 or in the range [1, n2].1 and n2 are not the starting points of any snake or ladder.Problem Overview: You are given an n x n snakes and ladders board where cells are labeled from 1 to n^2 in a boustrophedon (zigzag) order starting from the bottom row. From a cell, you roll a dice (1–6) and move forward. If the destination cell contains a snake or ladder, you must move to its target. The task is to compute the minimum number of dice throws required to reach cell n^2.
Approach 1: Breadth-First Search (BFS) (Time: O(n^2), Space: O(n^2))
This board naturally forms an unweighted graph where each cell is a node and edges represent dice outcomes from +1 to +6. Use Breadth-First Search to explore positions level by level, where each BFS layer corresponds to one dice roll. For every position, simulate the six possible moves, convert the target cell number into its 2D board coordinates, and check whether a snake or ladder redirects the move. Maintain a visited array to avoid revisiting cells. BFS guarantees the first time you reach n^2 is the minimum number of moves because all edges have equal cost. This approach is the standard and most efficient solution.
Approach 2: Dijkstra's Algorithm Adaptation (Time: O(n^2 log(n^2)), Space: O(n^2))
You can also model the board as a weighted graph and apply Dijkstra’s algorithm. Each node represents a board cell and each dice roll produces edges to the next six cells. The weight of each edge is 1 since every dice throw counts as one move. Using a priority queue, repeatedly expand the node with the smallest number of moves so far. Snake or ladder jumps are applied immediately when computing neighbors. Although this works correctly, the extra log factor from the priority queue makes it slower than BFS for this problem because all edges have identical weight. BFS is typically preferred for unweighted graphs.
The tricky part of the implementation is converting a cell number into board coordinates because rows alternate direction. Compute the row using integer division, then reverse the column index for every other row. This mapping step converts the linear position into the correct matrix index.
Recommended for interviews: BFS is the expected solution. It models the board as an unweighted graph and finds the shortest path in O(n^2) time. Showing the BFS traversal with a visited set demonstrates strong understanding of graph traversal on a grid-like structure stored in an array. Mentioning the Dijkstra alternative shows awareness of shortest-path algorithms, but BFS is simpler and optimal here.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(n^2) | O(n^2) | Best choice for this problem since the board forms an unweighted graph and BFS guarantees the shortest path in dice rolls. |
| Dijkstra's Algorithm Adaptation | O(n^2 log(n^2)) | O(n^2) | Useful if edges had different weights; works here but adds unnecessary priority queue overhead. |