Snakes and Ladders — Solution in Python, Java & C++
Snakes and Ladders solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and matrix.
Snakes and Ladders is a medium coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google, Microsoft and Zomato interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Breadth-First Search
- Asked at: Amazon, Google, Microsoft, Zomato, Hulu
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an n x n board whose squares are numbered 1 to n² in boustrophedon order: starting at the bottom-left and alternating direction each row.
From square x you may move to any of x+1 … x+6 that exists. If that square holds a value other than -1, you are immediately carried to that square instead. Return the least number of moves needed to reach square n², or -1 if it is unreachable.
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
Example 2
Input: board = [[-1,-1],[-1,3]]
Output: 1
Example 3
Input: board = [[-1,-1,-1],[-1,9,8],[-1,8,9]]
Output: 1
Constraints
2 <= board.length <= 8board[i].length == board.lengthboard[i][j] is -1 or in the range [1, n²]Squares 1 and n² never carry a snake or ladder.
Hints for Snakes and Ladders
Hint 1
Every move costs one, so breadth-first search over the squares finds the minimum.
Hint 2
The trickiest part is the numbering — write a helper that maps a square number to its row and column.
Hint 3
A snake or ladder is taken once on landing; do not follow a chain of them.
How to solve Snakes and Ladders
BFS over square numbers, with a helper mapping a square to its boustrophedon (row, col); a snake or ladder redirects the landing once.
Approach
value_at(square)computesrow = n - 1 - (square-1) // nand flips the column on alternate rows.- BFS from square 1; for each die roll
1..6, land, apply any redirect, enqueue if unseen. - Return the distance at
n², or -1.
Why it works
Every move costs one regardless of the roll, so BFS gives the minimum; redirects are applied exactly once per landing as the rules state.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- Do not chain a ladder into another ladder — only the landing square's redirect applies.
Reference solution
Python
from collections import deque
def snakesAndLadders(board) -> int:
n = len(board)
target = n * n
def value_at(square):
quotient, remainder = divmod(square - 1, n)
row = n - 1 - quotient
col = remainder if quotient % 2 == 0 else n - 1 - remainder
return board[row][col]
dist = [-1] * (target + 1)
dist[1] = 0
queue = deque([1])
while queue:
square = queue.popleft()
if square == target:
return dist[square]
for step in range(1, 7):
landing = square + step
if landing > target:
break
jump = value_at(landing)
destination = landing if jump == -1 else jump
if dist[destination] == -1:
dist[destination] = dist[square] + 1
queue.append(destination)
return -1Java
public static int snakesAndLadders(int[][] board) {
int n = board.length;
int target = n * n;
int[] dist = new int[target + 1];
Arrays.fill(dist, -1);
dist[1] = 0;
Deque<Integer> queue = new ArrayDeque<>();
queue.addLast(1);
while (!queue.isEmpty()) {
int square = queue.pollFirst();
if (square == target) return dist[square];
for (int step = 1; step <= 6 && square + step <= target; step++) {
int landing = square + step;
int quotient = (landing - 1) / n;
int remainder = (landing - 1) % n;
int row = n - 1 - quotient;
int col = quotient % 2 == 0 ? remainder : n - 1 - remainder;
int jump = board[row][col];
int destination = jump == -1 ? landing : jump;
if (dist[destination] == -1) {
dist[destination] = dist[square] + 1;
queue.addLast(destination);
}
}
}
return -1;
}C++
int snakesAndLadders(vector<vector<int>>& board) {
int n = (int) board.size();
int target = n * n;
vector<int> dist(target + 1, -1);
dist[1] = 0;
vector<int> queue;
queue.push_back(1);
size_t head = 0;
while (head < queue.size()) {
int square = queue[head++];
if (square == target) return dist[square];
for (int step = 1; step <= 6 && square + step <= target; step++) {
int landing = square + step;
int quotient = (landing - 1) / n;
int remainder = (landing - 1) % n;
int row = n - 1 - quotient;
int col = quotient % 2 == 0 ? remainder : n - 1 - remainder;
int jump = board[row][col];
int destination = jump == -1 ? landing : jump;
if (dist[destination] == -1) {
dist[destination] = dist[square] + 1;
queue.push_back(destination);
}
}
}
return -1;
}JavaScript
var snakesAndLadders = function(board) {
const n = board.length;
const target = n * n;
const valueAt = function(square) {
const quotient = Math.floor((square - 1) / n);
const remainder = (square - 1) % n;
const row = n - 1 - quotient;
const col = quotient % 2 === 0 ? remainder : n - 1 - remainder;
return board[row][col];
};
const dist = [];
for (let i = 0; i <= target; i++) dist.push(-1);
dist[1] = 0;
const queue = [1];
let head = 0;
while (head < queue.length) {
const square = queue[head++];
if (square === target) return dist[square];
for (let step = 1; step <= 6 && square + step <= target; step++) {
const landing = square + step;
const jump = valueAt(landing);
const destination = jump === -1 ? landing : jump;
if (dist[destination] === -1) {
dist[destination] = dist[square] + 1;
queue.push(destination);
}
}
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal