Log inSign up
mediumLeetCodeNot Started

Snakes and Ladders

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

You are given an n x n integer matrix board where the cells are labeled from 1 to n^2 in a Boustrophedon style (starting from the bottom-left of the board, alternating directions row by row).

You start on square 1 of the board. In each turn, from square curr, you choose a destination square next with a label in the range [curr + 1, min(curr + 6, n^2)]. This choice simulates the roll of a 6-sided die.

If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.

You do not move to snakes/ladders again after landing on their destination (no chained snake/ladder jumps).

Return the least number of dice rolls required to reach square n^2. If it is not possible to reach the square, return -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 do not have any snakes or ladders.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Map 1D sequential labels to 2D Boustrophedon zigzag matrix coordinates.
  • Formulate game state transitions as an unweighted directed graph.
  • Apply Breadth-First Search (BFS) for minimal step discovery.
  • Handle non-chaining snake/ladder destinations and cycle avoidance.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever a turn-based board game requires finding the 'minimum turns or moves' with uniform cost transitions (like die rolls), model each square as a graph vertex and use Breadth-First Search (BFS) rather than DFS or Dijkstra.

1. DFS with Visited Depth Tracking

Intuition

Explore all possible sequences of die rolls (1 to 6) recursively using Depth-First Search. Maintain a minRolls array where minRolls[sq] stores the minimum rolls found so far to reach square sq. If current rolls >= minRolls[sq], prune the branch. Return minRolls[N^2].

Algorithm

  1. Create helper getPos(sq, n) to map square number to (row, col).
  2. Initialize minRolls array of size n2 + 1 with infinity, set minRolls[1] = 0.
  3. Define dfs(curr, rolls):
  4. If rolls >= minRolls[curr], return.
  5. minRolls[curr] = rolls.
  6. If curr == n * n, return.
  7. For die = 1 to 6:
  8. next = curr + die
  9. If next > n * n, break.
  10. destination = board[r][c] != -1 ? board[r][c] : next
  11. dfs(destination, rolls + 1)
  12. Run dfs(1, 0).
  13. Return minRolls[n*n] == infinity ? -1 : minRolls[n*n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6std::pair<int, int> getCoordinates(int sq, int n) {
7 int r = n - 1 - (sq - 1) / n;
8 int c = (sq - 1) % n;
9 if (((sq - 1) / n) % 2 == 1) {
10 c = n - 1 - c;
11 }
12 return {r, c};
13}
14
15void dfs(int curr, int rolls, int n, const std::vector<std::vector<int>>& board, std::vector<int>& minRolls) {
16 if (rolls >= minRolls[curr]) return;
17 minRolls[curr] = rolls;
18 if (curr == n * n) return;
19
20 for (int die = 1; die <= 6 && curr + die <= n * n; ++die) {
21 int next = curr + die;
22 auto [r, c] = getCoordinates(next, n);
23 int dest = (board[r][c] != -1) ? board[r][c] : next;
24 dfs(dest, rolls + 1, n, board, minRolls);
25 }
26}
27
28int snakesAndLaddersDFS(std::vector<std::vector<int>>& board) {
29 int n = board.size();
30 std::vector<int> minRolls(n * n + 1, INT_MAX);
31 dfs(1, 0, n, board, minRolls);
32 return minRolls[n * n] == INT_MAX ? -1 : minRolls[n * n];
33}
34
35int main() {
36 std::vector<std::vector<int>> board = {{-1,-1},{-1,3}};
37 std::cout << "Snakes and Ladders (DFS): " << snakesAndLaddersDFS(board) << std::endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(6^(N^2)) worst case without aggressive pruning because each square branches into up to 6 choices.
  • Space complexity: O(N^2) for the recursion call stack and distance array.

2. Dijkstra's Algorithm

Intuition

Although edge weights are uniform (1), Dijkstra's algorithm using a min-heap guarantees visiting nodes in non-decreasing order of total moves. Priority queue contains (rolls, square). It serves as a bridge showing that non-uniform generalizations (such as variable roll costs) reduce to Dijkstra.

Algorithm

  1. Initialize dist array of size n2 + 1 with infinity, set dist[1] = 0.
  2. Push (0, 1) into priority queue.
  3. While priority queue is not empty:
  4. Pop (rolls, curr). If curr == n * n, return rolls.
  5. If rolls > dist[curr], continue.
  6. For die = 1 to 6:
  7. next = curr + die
  8. If next > n * n, break.
  9. dest = board[r][c] != -1 ? board[r][c] : next
  10. If rolls + 1 < dist[dest]:
  11. dist[dest] = rolls + 1
  12. Push (rolls + 1, dest) into priority queue.
  13. Return -1 if target is unreachable.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <climits>
5
6std::pair<int, int> getPos(int sq, int n) {
7 int r = n - 1 - (sq - 1) / n;
8 int c = (sq - 1) % n;
9 if (((sq - 1) / n) % 2 == 1) c = n - 1 - c;
10 return {r, c};
11}
12
13int snakesAndLaddersDijkstra(std::vector<std::vector<int>>& board) {
14 int n = board.size();
15 std::vector<int> dist(n * n + 1, INT_MAX);
16 std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;
17
18 dist[1] = 0;
19 pq.push({0, 1});
20
21 while (!pq.empty()) {
22 auto [rolls, curr] = pq.top();
23 pq.pop();
24
25 if (curr == n * n) return rolls;
26 if (rolls > dist[curr]) continue;
27
28 for (int die = 1; die <= 6 && curr + die <= n * n; ++die) {
29 int next = curr + die;
30 auto [r, c] = getPos(next, n);
31 int dest = (board[r][c] != -1) ? board[r][c] : next;
32 if (rolls + 1 < dist[dest]) {
33 dist[dest] = rolls + 1;
34 pq.push({rolls + 1, dest});
35 }
36 }
37 }
38 return -1;
39}
40
41int main() {
42 std::vector<std::vector<int>> board = {{-1,-1},{-1,3}};
43 std::cout << "Snakes and Ladders (Dijkstra): " << snakesAndLaddersDijkstra(board) << std::endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N^2 log(N^2)) due to priority queue insertions.
  • Space complexity: O(N^2) for the priority queue and distance array.

3. Breadth-First Search (BFS)

Intuition

Because each die roll constitutes exactly one step (uniform weight = 1), standard BFS guarantees that the first time square N2 is discovered or popped, it is reached via the minimal number of dice rolls. Marking destination squares visited when pushed prevents redundant queuing and eliminates cycles.

Algorithm

  1. Create helper getCoordinates(sq, n):
  2. row = n - 1 - (sq - 1) / n
  3. col = (sq - 1) % n
  4. If ((sq - 1) / n) % 2 == 1, col = n - 1 - col.
  5. Initialize queue with (sq = 1, rolls = 0).
  6. Initialize visited boolean array of size n2 + 1 with false, set visited[1] = true.
  7. While queue is not empty:
  8. Pop (curr, rolls).
  9. If curr == n * n, return rolls.
  10. For die = 1 to 6:
  11. next = curr + die
  12. If next > n * n, break.
  13. dest = board[r][c] != -1 ? board[r][c] : next
  14. If !visited[dest]:
  15. visited[dest] = true
  16. Push (dest, rolls + 1) into queue.
  17. Return -1 if queue becomes empty without reaching n2.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5std::pair<int, int> getCoordinates(int sq, int n) {
6 int r = n - 1 - (sq - 1) / n;
7 int c = (sq - 1) % n;
8 if (((sq - 1) / n) % 2 == 1) {
9 c = n - 1 - c;
10 }
11 return {r, c};
12}
13
14int snakesAndLadders(std::vector<std::vector<int>>& board) {
15 int n = board.size();
16 std::vector<bool> visited(n * n + 1, false);
17 std::queue<std::pair<int, int>> q;
18
19 q.push({1, 0}); // {square, rolls}
20 visited[1] = true;
21
22 while (!q.empty()) {
23 auto [curr, rolls] = q.front();
24 q.pop();
25
26 if (curr == n * n) return rolls;
27
28 for (int die = 1; die <= 6 && curr + die <= n * n; ++die) {
29 int next = curr + die;
30 auto [r, c] = getCoordinates(next, n);
31 int dest = (board[r][c] != -1) ? board[r][c] : next;
32
33 if (!visited[dest]) {
34 visited[dest] = true;
35 q.push({dest, rolls + 1});
36 }
37 }
38 }
39
40 return -1;
41}
42
43int main() {
44 std::vector<std::vector<int>> board = {{-1,-1},{-1,3}};
45 std::cout << "Optimal Snakes and Ladders (BFS): " << snakesAndLadders(board) << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N^2) where N is the board dimension. Each square 1 to N^2 is pushed into the queue at most once, and explores at most 6 die rolls.
  • Space complexity: O(N^2) for the queue and visited array.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS with PruningO(6^(N^2))O(N^2)Straightforward recursive formulation.Exponential worst case; prone to deep recursion and redundant subpath evaluations.
2.Dijkstra's AlgorithmO(N^2 log(N^2))O(N^2)Guarantees shortest path order even if edge costs were non-uniform.Min-heap overhead is unnecessary since all edge weights equal 1.
3.Breadth-First Search (BFS)OptimalO(N^2)O(N^2)Optimal linear time; discovers the shortest path level-by-level with standard queue.Requires careful mapping of 1D coordinates to 2D zigzag grid.

Common Pitfalls & Crucial Edge Cases

Chaining snakes and ladders (e.g., if dest has another ladder, taking it too).

The problem states you only move to the destination of the snake/ladder once per die roll.

Incorrect row/col mapping for Boustrophedon layout.

Remember row 0 in matrix is the top of the board, while square 1 is at the bottom-left (row n - 1).

Crucial Edge Cases to Validate:

  • Direct roll from 1 to n^2 in 1 move (n = 2, n^2 = 4) — Die roll 3 lands directly on square 4, returns 1.
  • Board where destination n^2 is completely blocked or only leads to snakes — Queue empties without reaching n2, returns -1.
  • Snake loop (e.g. sq 5 has snake to 2, sq 2 leads to 5) — Visited array prevents re-adding visited squares, avoiding infinite loops.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State immediately: 'Unweighted shortest path problem with uniform step cost of 1 die roll -> BFS is optimal.'
  2. Write out the getCoordinates(sq, n) conversion clearly as a separate helper function to keep the BFS clean.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why should we mark dest as visited when pushing to the queue instead of next?

2.Can a player take a ladder immediately after landing on another ladder (chained ladders)?

3.How does the column coordinate c behave in Boustrophedon ordering?

Back to DSA Sheet