Snakes and Ladders solution and explanation
Cisco
Google
9 more videos on this problem
Snakes and Ladders - Leetcode 909 - PythonNeetCode · 21:22 · 77K views
Snakes and Ladders | Detailed Reason | Leetcode 909 | codestorywithMIKcodestorywithMIK · 44:24 · 22K views
G-06 BFS Problem Type-1 II Simple BFS II Snakes an Ladders || Leetcode - 909Aryan Mittal · 24:18 · 7K views
LeetCode 909. Snakes and Ladders Explanation and Solutionhappygirlzt · 13:30 · 6K views
Leetcode 909 Snakes and Ladders | Google Meta | Backtracking template | SDE Sheet belowCoding Decoded · 11:30 · 6K views
Snakes and Ladders | Matrix Flattening | Leetcode 909Techdose · 29:29 · 3K views
Leetcode 909 Snakes and Ladders (Java)TheAnalyticGuy · 12:22 · 1K views
Daily Leetcode #1029: Jan 24, 2023 - 909. Snakes and LaddersProgramming Live with Larry · 15:30 · 923 views
LeetCode in Python 909. Snakes and Ladders | BFS Approach - Michelle小梦想家Michelle小梦想家 · 34:25 · 853 views
EN) Leetcode 909. Snakes and LaddersJBKClass · 8:10 · 380 views
The problem
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
nextwith 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
nexthas a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move tonext. - 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 is2. You follow the ladder to square3, but do not follow the subsequent ladder to4.
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-1or in the range[1, n2].- The squares labeled
1andn2are 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.
from collections import deque
class Solution:
def snakesAndLadders(self, board):
n = len(board)
def get_board_value(num):
r, c = divmod(num-1, n)
if r % 2 == 0:
return board[n - 1 - r][c]
else:
return board[n - 1 - r][n - 1 - c]
visited = set()
queue = deque([(1, 0)])
visited.add(1)
while queue:
position, moves = queue.popleft()
for i in range(1, 7):
next_position = position + i
if next_position > n * n:
continue
board_value = get_board_value(next_position)
if board_value != -1:
next_position = board_value
if next_position == n * n:
return moves + 1
if next_position not in visited:
visited.add(next_position)
queue.append((next_position, moves + 1))
return -1import java.util.*;
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
int[] flattenBoard = new int[n * n + 1];
int index = 1;
boolean leftToRight = true;
for (int i = n - 1; i >= 0; i--) {
if (leftToRight) {
for (int j = 0; j < n; j++) {
flattenBoard[index++] = board[i][j];
}
} else {
for (int j = n - 1; j >= 0; j--) {
flattenBoard[index++] = board[i][j];
}
}
leftToRight = !leftToRight;
}
Queue<int[]> queue = new LinkedList<>();
boolean[] visited = new boolean[n * n + 1];
queue.offer(new int[]{1, 0});
visited[1] = true;
while (!queue.isEmpty()) {
int[] node = queue.poll();
int pos = node[0];
int moves = node[1];
for (int i = 1; i <= 6; i++) {
int nextPos = pos + i;
if (nextPos <= n * n) {
if (flattenBoard[nextPos] != -1) {
nextPos = flattenBoard[nextPos];
}
if (!visited[nextPos]) {
if (nextPos == n * n) return moves + 1;
visited[nextPos] = true;
queue.offer(new int[]{nextPos, moves + 1});
}
}
}
}
return -1;
}
}#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
vector<int> flattenBoard(n * n + 1, -1);
int idx = 1;
bool leftToRight = true;
for (int i = n - 1; i >= 0; --i) {
if (leftToRight) {
for (int j = 0; j < n; ++j) {
flattenBoard[idx++] = board[i][j];
}
} else {
for (int j = n - 1; j >= 0; --j) {
flattenBoard[idx++] = board[i][j];
}
}
leftToRight = !leftToRight;
}
queue<pair<int, int>> q;
vector<bool> visited(n * n + 1, false);
q.push({1, 0});
visited[1] = true;
while (!q.empty()) {
auto [pos, moves] = q.front();
q.pop();
if (pos == n * n) return moves;
for (int i = 1; i <= 6; ++i) {
int nextPos = pos + i;
if (nextPos <= n * n) {
if (flattenBoard[nextPos] != -1) {
nextPos = flattenBoard[nextPos];
}
if (!visited[nextPos]) {
visited[nextPos] = true;
q.push({nextPos, moves + 1});
}
}
}
}
return -1;
}
};var snakesAndLadders = function(board) {
const n = board.length;
function getBoardValue(number) {
const q = Math.floor((number - 1) / n), r = (number - 1) % n;
const row = n - 1 - q, col = (q % 2 === 0) ? r : (n - 1 - r);
return board[row][col];
}
const visited = new Array(n * n + 1).fill(false);
const queue = [[1, 0]];
visited[1] = true;
while (queue.length) {
const [pos, moves] = queue.shift();
for (let i = 1; i <= 6; i++) {
let nextPos = pos + i;
if (nextPos > n * n) continue;
const value = getBoardValue(nextPos);
if (value !== -1) nextPos = value;
if (nextPos === n * n) return moves + 1;
if (!visited[nextPos]) {
visited[nextPos] = true;
queue.push([nextPos, moves + 1]);
}
}
}
return -1;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
typedef struct {
int position;
int moves;
} QueueNode;
typedef struct {
QueueNode* nodes;
int front;
int rear;
int capacity;
} Queue;
Queue* createQueue(int capacity) {
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->capacity = capacity;
queue->front = queue->rear = 0;
queue->nodes = (QueueNode*)malloc(capacity * sizeof(QueueNode));
return queue;
}
bool isQueueEmpty(Queue* queue) {
return queue->front == queue->rear;
}
void enqueue(Queue* queue, int position, int moves) {
queue->nodes[queue->rear++] = (QueueNode){position, moves};
}
QueueNode dequeue(Queue* queue) {
return queue->nodes[queue->front++];
}
int snakesAndLadders(int** board, int boardSize, int* boardColSize) {
int n = boardSize;
int *flattenBoard = (int *)malloc((n * n + 1) * sizeof(int));
int index = 1;
bool flip = false;
for (int i = n - 1; i >= 0; i--) {
if (flip) {
for (int j = n - 1; j >= 0; j--) {
flattenBoard[index++] = board[i][j];
}
} else {
for (int j = 0; j < n; j++) {
flattenBoard[index++] = board[i][j];
}
}
flip = !flip;
}
bool *visited = (bool *)calloc(n * n + 1, sizeof(bool));
Queue* queue = createQueue(n * n);
enqueue(queue, 1, 0);
visited[1] = true;
while (!isQueueEmpty(queue)) {
QueueNode node = dequeue(queue);
int pos = node.position;
int moves = node.moves;
for (int i = 1; i <= 6; i++) {
int nextPos = pos + i;
if (nextPos <= n * n) {
if (flattenBoard[nextPos] != -1) {
nextPos = flattenBoard[nextPos];
}
if (!visited[nextPos]) {
if (nextPos == n * n) {
free(flattenBoard);
free(visited);
free(queue->nodes);
free(queue);
return moves + 1;
}
visited[nextPos] = true;
enqueue(queue, nextPos, moves + 1);
}
}
}
}
free(flattenBoard);
free(visited);
free(queue->nodes);
free(queue);
return -1;
}using System;
using System.Collections.Generic;
public class Solution {
public int SnakesAndLadders(int[][] board) {
int n = board.Length;
int CalculatePosition(int num) {
int quot = (num - 1) / n, rem = (num - 1) % n;
int row = n - 1 - quot;
int col = (quot % 2 == 0) ? rem : (n - 1 - rem);
return board[row][col];
}
var visited = new bool[n * n + 1];
Queue<(int, int)> queue = new Queue<(int, int)>();
queue.Enqueue((1, 0));
visited[1] = true;
while (queue.Count > 0) {
var (pos, moves) = queue.Dequeue();
for (int i = 1; i <= 6; i++) {
int nextPos = pos + i;
if (nextPos > n * n) continue;
int boardValue = CalculatePosition(nextPos);
if (boardValue != -1) nextPos = boardValue;
if (!visited[nextPos]) {
if (nextPos == n * n) return moves + 1;
visited[nextPos] = true;
queue.Enqueue((nextPos, moves + 1));
}
}
}
return -1;
}
}The Python solution uses BFS for exploring possible moves, ensuring all reachable squares account for snakes and ladders. A helper function maps board squares to positions in a flattened manner.
Time Complexity: O(n^2), processing each square once.
Space Complexity: O(n^2), required for queue processing and visited tracking.
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.
import heapq
class Solution:
def snakesAndLadders(self, board):
n = len(board)
def get_board_value(num):
r, c = divmod(num-1, n)
if r % 2 == 0:
return board[n - 1 - r][c]
else:
return board[n - 1 - r][n - 1 - c]
dist = {i: float('inf') for i in range(1, n*n + 1)}
dist[1] = 0
pq = [(0, 1)]
while pq:
current_dist, u = heapq.heappop(pq)
if u == n * n:
return current_dist
for dice in range(1, 7):
v = u + dice
if v <= n * n:
board_value = get_board_value(v)
if board_value != -1:
v = board_value
if current_dist + 1 < dist[v]:
dist[v] = current_dist + 1
heapq.heappush(pq, (dist[v], v))
return -1import java.util.*;
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
int[] dist = new int[n * n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[1] = 0;
int[] flattenBoard = new int[n * n + 1];
Arrays.fill(flattenBoard, -1);
int index = 1;
boolean leftToRight = true;
for (int i = n - 1; i >= 0; --i) {
if (leftToRight) {
for (int j = 0; j < n; ++j) {
flattenBoard[index++] = board[i][j];
}
} else {
for (int j = n - 1; j >= 0; --j) {
flattenBoard[index++] = board[i][j];
}
}
leftToRight = !leftToRight;
}
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, 1});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int u = current[1];
int currentDist = current[0];
if (u == n * n) return currentDist;
for (int dice = 1; dice <= 6; dice++) {
int v = u + dice;
if (v <= n * n) {
v = flattenBoard[v] != -1 ? flattenBoard[v] : v;
if (currentDist + 1 < dist[v]) {
dist[v] = currentDist + 1;
pq.offer(new int[]{dist[v], v});
}
}
}
}
return -1;
}
}#include <vector>
#include <queue>
using namespace std;
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
vector<int> dist(n * n + 1, INT_MAX);
vector<int> flattenBoard(n * n + 1, -1);
int idx = 1;
bool leftToRight = true;
for (int i = n - 1; i >= 0; --i) {
if (leftToRight) {
for (int j = 0; j < n; ++j) {
flattenBoard[idx++] = board[i][j];
}
} else {
for (int j = n - 1; j >= 0; --j) {
flattenBoard[idx++] = board[i][j];
}
}
leftToRight = !leftToRight;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 1});
dist[1] = 0;
while (!pq.empty()) {
auto [current_dist, u] = pq.top(); pq.pop();
if (u == n * n) return current_dist;
for (int dice = 1; dice <= 6; ++dice) {
int v = u + dice;
if (v <= n * n) {
v = flattenBoard[v] != -1 ? flattenBoard[v] : v;
if (current_dist + 1 < dist[v]) {
dist[v] = current_dist + 1;
pq.push({dist[v], v});
}
}
}
}
return -1;
}var snakesAndLadders = function(board) {
const n = board.length;
function getBoardValue(number) {
const q = Math.floor((number - 1) / n), r = (number - 1) % n;
const row = n - 1 - q;
const col = q % 2 === 0 ? r : n - 1 - r;
return board[row][col];
}
const dist = Array(n * n + 1).fill(Infinity);
dist[1] = 0;
const pq = new MinPriorityQueue({priority: x => x[0]});
pq.enqueue([0, 1]);
while (!pq.isEmpty()) {
const [currentDist, u] = pq.dequeue().element;
if (u === n * n) return currentDist;
for (let dice = 1; dice <= 6; dice++) {
let v = u + dice;
if (v <= n * n) {
let value = getBoardValue(v);
if (value !== -1) v = value;
if (currentDist + 1 < dist[v]) {
dist[v] = currentDist + 1;
pq.enqueue([dist[v], v]);
}
}
}
}
return -1;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#define MIN(a,b) ((a)<(b)?(a):(b))
typedef struct {
int node, cost;
} Node;
typedef struct {
Node* data;
int size, capacity;
} MinHeap;
MinHeap* createMinHeap(int capacity) {
MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));
minHeap->data = (Node*)malloc(sizeof(Node) * capacity);
minHeap->size = 0;
minHeap->capacity = capacity;
return minHeap;
}
void swap(Node* a, Node* b) {
Node temp = *a;
*a = *b;
*b = temp;
}
void minHeapify(MinHeap* minHeap, int index) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < minHeap->size && minHeap->data[left].cost < minHeap->data[smallest].cost)
smallest = left;
if (right < minHeap->size && minHeap->data[right].cost < minHeap->data[smallest].cost)
smallest = right;
if (smallest != index) {
swap(&minHeap->data[index], &minHeap->data[smallest]);
minHeapify(minHeap, smallest);
}
}
Node extractMin(MinHeap* minHeap) {
Node root = minHeap->data[0];
minHeap->data[0] = minHeap->data[minHeap->size - 1];
minHeap->size--;
minHeapify(minHeap, 0);
return root;
}
void insertMinHeap(MinHeap* minHeap, Node node) {
minHeap->data[minHeap->size] = node;
int i = minHeap->size++;
while (i && minHeap->data[i].cost < minHeap->data[(i - 1) / 2].cost) {
swap(&minHeap->data[i], &minHeap->data[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
int snakesAndLadders(int** board, int boardSize, int* boardColSize) {
int n = boardSize;
int destination = n * n;
int *flattenBoard = (int *)malloc((destination + 1) * sizeof(int));
int idx = 1;
bool isLTR = true;
for (int i = n - 1; i >= 0; i--) {
if (isLTR) {
for (int j = 0; j < n; j++)
flattenBoard[idx++] = board[i][j];
} else {
for (int j = n - 1; j >= 0; j--)
flattenBoard[idx++] = board[i][j];
}
isLTR = !isLTR;
}
int *dist = (int *)malloc((destination + 1) * sizeof(int));
for (int i = 0; i <= destination; i++) dist[i] = INFINITY;
dist[1] = 0;
MinHeap* minHeap = createMinHeap(destination);
insertMinHeap(minHeap, (Node){1, 0});
while (minHeap->size > 0) {
Node minNode = extractMin(minHeap);
int u = minNode.node;
if (u == destination) {
free(flattenBoard);
free(minHeap->data);
free(minHeap);
free(dist);
return dist[u];
}
for (int dice = 1; dice <= 6; dice++) {
int v = u + dice;
if (v <= destination) {
if (flattenBoard[v] != -1) v = flattenBoard[v];
if (dist[u] + 1 < dist[v]) {
dist[v] = dist[u] + 1;
insertMinHeap(minHeap, (Node){v, dist[v]});
}
}
}
}
free(flattenBoard);
free(minHeap->data);
free(minHeap);
free(dist);
return -1;
}using System;
using System.Collections.Generic;
public class Solution {
public int SnakesAndLadders(int[][] board) {
int n = board.Length;
int[] dist = new int[n * n + 1];
for (int i = 0; i < dist.Length; i++)
dist[i] = int.MaxValue;
dist[1] = 0;
int[] flattenBoard = new int[n * n + 1];
int index = 1;
bool leftToRight = true;
for (int i = n - 1; i >= 0; --i) {
if (leftToRight) {
for (int j = 0; j < n; j++) {
flattenBoard[index++] = board[i][j];
}
} else {
for (int j = n - 1; j >= 0; j--) {
flattenBoard[index++] = board[i][j];
}
}
leftToRight = !leftToRight;
}
SortedSet<(int, int)> pq = new SortedSet<(int, int)>();
pq.Add((0, 1));
while (pq.Count > 0) {
var (currentDist, u) = pq.Min;
pq.Remove(pq.Min);
if (u == n * n) return currentDist;
for (int dice = 1; dice <= 6; dice++) {
int v = u + dice;
if (v <= n * n) {
if (flattenBoard[v] != -1) v = flattenBoard[v];
if (currentDist + 1 < dist[v]) {
if (pq.Contains((dist[v], v))) {
pq.Remove((dist[v], v));
}
dist[v] = currentDist + 1;
pq.Add((dist[v], v));
}
}
}
}
return -1;
}
}Employing Python's native min-heap via heapq, the solution adapts shortest path logic with move cost checks and prioritization of paths.
Time Complexity: O(n^2 log(n^2)), considering dynamic moves estimate increase influenced by heap rebalancing.
Space Complexity: O(n^2) driven by priority queue management.
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.
function snakesAndLadders(board: number[][]): number {
const n = board.length;
const q: number[] = [1];
const m = n * n;
const vis: boolean[] = Array(m + 1).fill(false);
vis[1] = true;
for (let ans = 0; q.length > 0; ans++) {
const nq: number[] = [];
for (const x of q) {
if (x === m) {
return ans;
}
for (let y = x + 1; y <= Math.min(x + 6, m); y++) {
let i = Math.floor((y - 1) / n);
let j = (y - 1) % n;
if (i % 2 === 1) {
j = n - j - 1;
}
i = n - i - 1;
const z = board[i][j] === -1 ? y : board[i][j];
if (!vis[z]) {
vis[z] = true;
nq.push(z);
}
}
}
q.length = 0;
for (const x of nq) {
q.push(x);
}
}
return -1;
}func snakesAndLadders(board [][]int) int {
n := len(board)
q := []int{1}
m := n * n
vis := make([]bool, m+1)
vis[1] = true
for ans := 0; len(q) > 0; ans++ {
for k := len(q); k > 0; k-- {
x := q[0]
q = q[1:]
if x == m {
return ans
}
for y := x + 1; y <= min(x+6, m); y++ {
i, j := (y-1)/n, (y-1)%n
if i%2 == 1 {
j = n - j - 1
}
i = n - i - 1
z := y
if board[i][j] != -1 {
z = board[i][j]
}
if !vis[z] {
vis[z] = true
q = append(q, z)
}
}
}
}
return -1
}use std::collections::{HashSet, VecDeque};
impl Solution {
pub fn snakes_and_ladders(board: Vec<Vec<i32>>) -> i32 {
let n = board.len();
let m = (n * n) as i32;
let mut q = VecDeque::new();
q.push_back(1);
let mut vis = HashSet::new();
vis.insert(1);
let mut ans = 0;
while !q.is_empty() {
for _ in 0..q.len() {
let x = q.pop_front().unwrap();
if x == m {
return ans;
}
for y in x + 1..=i32::min(x + 6, m) {
let (mut i, mut j) = ((y - 1) / n as i32, (y - 1) % n as i32);
if i % 2 == 1 {
j = (n as i32 - 1) - j;
}
i = (n as i32 - 1) - i;
let z = if board[i as usize][j as usize] == -1 {
y
} else {
board[i as usize][j as usize]
};
if !vis.contains(&z) {
vis.insert(z);
q.push_back(z);
}
}
}
ans += 1;
}
-1
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) | Time Complexity: O(n^2), processing each square once. Space Complexity: O(n^2), required for queue processing and visited tracking. |
| Dijkstra's Algorithm Adaptation | Time Complexity: O(n^2 log(n^2)), considering dynamic moves estimate increase influenced by heap rebalancing. Space Complexity: O(n^2) driven by priority queue management. |
| BFS | – |
Complexity analysis
| 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. |
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.