Skip to main content
Talentd

Snakes and Ladders - Solution & Explanation

MediumArrayBreadth-First SearchMatrix31 min readAsked at: Amazon, Microsoft, Apple +9
Practice this problem

Problem Statement

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:

  • Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].
    • 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 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.

  • 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 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].length
  • 2 <= n <= 20
  • board[i][j] is either -1 or in the range [1, n2].
  • The squares labeled 1 and n2 are not the starting points of any snake or ladder.

Approach Overview

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 1: Breadth-First Search (BFS)

The Snakes and Ladders board can be seen as a graph where each square is a node, and an edge exists between node i and node j if you can move from square i to square j with a dice roll. Use BFS to efficiently explore this graph, ensuring each move accounts for ladders and snakes.

The solution flattens the 2D board to a 1D array while considering the Boustrophedon order. Then, using BFS, it processes nodes (squares) ensuring each is visited based on dice moves accounting for any ladders or snakes directly. It effectively exits on reaching the end square.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the board dimension, as each square is processed once.

Space Complexity: O(n^2), for storing the queue and visited status of squares.

Try this approach in the editor →

Approach 2: Dijkstra's Algorithm Adaptation

Dijkstra's Algorithm typically finds shortest paths in weighted graphs. Adapting it for an unweighted snakes and ladders board can ensure the fewest moves to reach the final square by evaluating and using priority. Each move is computed implicitly based on its dice-distance weight.

The C implementation uses a modified Dijkstra-like approach with direct BFS priority management via a min-heap to identify the least cost number of rolls to navigate the board to its end.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2 log(n^2)), given heap operations for prioritized traversal.

Space Complexity: O(n^2) for heap management.

Try this approach in the editor →

Approach 3: BFS

We can use the Breadth-First Search (BFS) method, starting from the starting point, moving forward 1 to 6 steps each time, and then checking for snakes or ladders. If there are any, move to the destination of the snake or ladder; otherwise, move to the next square.

Specifically, we use a queue q to store the current reachable square numbers, initially putting number 1 into the queue. At the same time, we use a set vis to record the squares that have been reached to avoid revisiting them, initially adding number 1 to the set vis.

In each operation, we take out the square number x at the front of the queue. If x is the endpoint, we can return the current number of steps. Otherwise, we move x forward 1 to 6 steps, setting the new number as y. If y falls outside the board, we skip it directly. Otherwise, we need to find the row and column corresponding to y. Since the row numbers decrease from bottom to top, and the column numbers depend on the parity of the row, we need to perform some calculations to get the row and column corresponding to y.

If the square corresponding to y has a snake or ladder, we need to move to the destination of the snake or ladder, denoted as z. If z has not been visited, we add z to the queue and set, allowing us to continue the breadth-first search.

If we ultimately cannot reach the endpoint, we return -1.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the side of the board.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS)

Time Complexity: O(n^2), where n is the board dimension, as each square is processed once.

Space Complexity: O(n^2), for storing the queue and visited status of squares.

Dijkstra's Algorithm Adaptation

Time Complexity: O(n^2 log(n^2)), given heap operations for prioritized traversal.

Space Complexity: O(n^2) for heap management.

BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 AdaptationO(n^2 log(n^2))O(n^2)Useful if edges had different weights; works here but adds unnecessary priority queue overhead.

Video Solution

Snakes and Ladders - Leetcode 909 - Python • NeetCode • 77,419 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Snakes and Ladders easy or hard?
Snakes and Ladders is generally considered a medium difficulty problem. The BFS idea is straightforward, but many candidates struggle with converting the linear cell numbers into the zigzag board coordinates and correctly handling snakes and ladders.
How to solve Snakes and Ladders in O(n^2)?
Model the board as a graph and perform Breadth-First Search starting from cell 1. For every position, simulate dice outcomes from 1 to 6, compute the next cell, and follow any snake or ladder immediately. Track visited cells to prevent cycles. BFS guarantees the shortest path, giving an O(n^2) time solution.
What is the best approach for Snakes and Ladders?
Breadth-First Search (BFS) is the best approach. The board can be modeled as an unweighted graph where each cell connects to the next six cells based on dice outcomes. BFS explores moves level by level, ensuring the first time the final cell is reached corresponds to the minimum number of dice throws. The overall complexity is O(n^2) time and O(n^2) space.
What data structure is used in Snakes and Ladders?
The main data structure is a queue used for Breadth-First Search. A visited array or set tracks which board cells have already been explored. The board itself is represented as a matrix, and positions are often converted between linear indices and matrix coordinates.
What is the time complexity of Snakes and Ladders?
The optimal BFS solution runs in O(n^2) time where n is the board dimension. Each of the n^2 cells is processed at most once, and from each cell up to six dice moves are checked. Space complexity is also O(n^2) due to the visited set and BFS queue.
Snakes and Ladders Python or Java solution approach?
Both Python and Java implementations typically use BFS with a queue. Convert the board cell number into matrix coordinates, simulate dice rolls from 1–6, apply snake or ladder jumps, and push unvisited cells into the queue. The first time the final cell is dequeued gives the minimum number of moves.
Is Snakes and Ladders asked at Google, Amazon, or Meta?
Snakes and Ladders appears in interviews that test graph traversal and BFS modeling. Variants of the problem have been reported in interviews at companies like Amazon and Google where candidates must convert a board representation into a graph and compute the shortest path.

Ready to solve this problem?

Practice Snakes and Ladders with our built-in code editor and test cases.

Practice on FleetCode
Previous

Most Profitable Path in a Tree