Loading…

mediumGraphsLC #909Sometimes asked

Snakes and Ladders

Q: How do you solve Snakes and Ladders using the BFS with a Distance Array approach?

When to use it: Offer as a tidy alternative that stores each square's distance instead of counting layers — handy if the interviewer also wants the distance to every square. This is the same BFS with different bookkeeping — instead of an explicit layer loop, each node carries its own distance. **Distance replaces the layer counter.** We keep an array `dist` where `dist[s]` is the minimum moves to reach square `s`, initialised to `-1` to mean 'not yet seen'. `dist[1] = 0` seeds the start. When we dequeue square `label`, BFS guarantees `dist[label]` is already its shortest distance, so any newly discovered neighbour `target` gets `dist[target] = dist[label] + 1`. **The dist array is also the visited set.** A square is unvisited exactly when its distance is still `-1`. Checking `dist[target] == -1` before relaxing both prevents re-enqueueing and preserves the shortest distance already recorded — because in unweighted BFS the *first* assignment is always the smallest. This folds two data structures (visited + distance) into one. **Reading off the answer.** We can return early the moment we set or pop `n²`, but it's just as clean to run BFS to completion and return `dist[n²]` — which is `-1` automatically if the goal was never reached. That uniform handling of the unreachable case is the small ergonomic win of this version. **Same forced-jump logic.** The coordinate conversion and the single-jump snake/ladder rule are identical to the layer version; only the move-counting mechanism changes. Pick whichever you find less error-prone under pressure — many people prefer the distance array because it removes the inner 'for each node in this layer' loop and its off-by-one risks. Time complexity: O(n²). Space complexity: O(n²).

LCPractice

Graphs · 11 of 34 · 11 min

You are given an n x n integer matrix board where the cells are labeled from 1 to n² 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. In each move, starting from square curr, you may choose a destination square next with a label in the range [curr + 1, min(curr + 6, n²)] (simulating a 6-sided die). If board[r][c] != -1, the square has a snake or ladder and you must move to board[r][c] (you do not roll again).

Return the least number of moves required to reach the square `n²`. If it is not possible to reach the square, return -1.

In plain English

Number the squares 1…n² following the snake-like path that starts at the bottom-left and zig-zags up. From any square you can jump 1–6 ahead (a dice roll). Landing on a snake or ladder forces you to its other end. We want the fewest dice rolls to reach the last square — a classic shortest-path-on-an-unweighted-graph question.

Examples

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
Note: From square 1 a roll to 2 takes the ladder to 15. From 15 reach 17, then 13 via the snake, then to 35 via the ladder, finishing at 36 (n²) in 4 moves.

Example 2

Input: board = [[-1,-1],[-1,3]]
Output: 1
Note: n=2 so n²=4. Square 1 is board[1][0]. A single roll can reach square 4 directly, so the answer is 1.

Example 3

Input: board = [[1,1,-1],[1,1,1],[-1,1,1]]
Output: -1
Note: Snakes/ladders that point back keep you from ever reaching the final square — BFS empties the queue and returns -1.

Constraints

n == board.length == board[i].length
2 ≤ n ≤ 20
grid[i][j] is either -1 or in the range [1, n²]
The squares labeled 1 and n² do not have any ladders or snakes

Clarifying questions4First question: How exactly are the squares numbered?Explore questions

Q1.How exactly are the squares numbered?
Boustrophedon: square 1 is the bottom-left cell, the bottom row runs left-to-right, the next row up runs right-to-left, and so on. I'll write a helper to convert a label back to (row, col).
Q2.If I land on a ladder/snake, do I roll again or chain to another ladder?
Neither — the jump is forced and applied exactly once. You do not roll from the landing square, and a destination that itself holds a snake/ladder is not chained.
Q3.Since every move is one dice roll, are all edges equal weight?
Yes — each move costs 1 regardless of where the die or a ladder takes you. Equal weights mean BFS gives the shortest path; Dijkstra would be overkill.
Q4.What if the end square is unreachable?
Return -1. BFS detects this when the queue empties before n² is ever dequeued.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

This is a shortest-path problem on an unweighted graph, so the answer is BFS. Flatten the n×n board into squares 1…n² using boustrophedon (snake) numbering, where each square has up to 6 outgoing edges (a dice roll of 1–6) and snakes/ladders are forced jumps to another square. BFS from square 1 layer by layer; the first time you dequeue n² the layer count is the minimum number of moves. If you exhaust the queue without reaching n², return −1. O(n²) time and space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise 'minimum number of moves on an unweighted graph' as BFS, can model squares as nodes with up-to-6 edges, and can correctly translate the boustrophedon (snake) numbering into (row, col) coordinates.

Where candidates slip

Using DFS (which finds *a* path, not the shortest), chaining snakes/ladders (a jump should be applied only once), or getting the boustrophedon row/column conversion wrong.

How to stand out

State 'unweighted ⇒ BFS' explicitly, isolate the coordinate conversion into a clean helper, mark visited at enqueue keyed by destination, and note that a snake/ladder is a single forced jump, never chained.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	BFS Layer-by-Layer (Optimal)Optimal	`O(n²)`	`O(n²)`	Lead with this. Phrase it as 'minimum moves on an unweighted graph is textbook BFS — the only twist is the snake-style numbering'.	Read
2	BFS with a Distance Array	`O(n²)`	`O(n²)`	Offer as a tidy alternative that stores each square's distance instead of counting layers — handy if the interviewer also wants the distance to every square.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFewest moves to reach square n²Do edges have equal cost?Yes (1 roll each)No / weightedExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

BFS Layer-by-Layer (Optimal)

TimeO(n²)SpaceO(n²)

Lead with this. Phrase it as 'minimum moves on an unweighted graph is textbook BFS — the only twist is the snake-style numbering'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each square 1…n² is a node. From square x you can roll to x+1 … x+6, so each node has up to 6 outgoing edges, every edge costing one move.

2Hint 2Explore hint

Equal edge cost ⇒ BFS finds the fewest moves. Process the queue one layer at a time and the layer number is the move count.

3Hint 3Explore hint

The fiddly part is mapping a label back to (row, col): rows are numbered bottom-up, and alternate direction. Write a helper, and remember a snake/ladder is a single forced jump.

A · Core idea

Strip away the board-game dressing and this is the most standard shortest-path problem there is.

Why BFS and not DFS or Dijkstra. A 'move' is one dice roll, and every roll costs exactly the same — one. When all edges have equal weight, BFS explores the graph in concentric layers of increasing distance, so the first time it reaches a node it has reached it by a shortest path. DFS would find a path but not necessarily the shortest, and Dijkstra's priority queue is wasted machinery on a uniform-cost graph. So the moment you read 'least number of moves' over equal-cost edges, BFS is the answer.

Modeling the board as a graph. Each square x (1…n²) is a node. The legal moves from x are exactly the labels x+1 through min(x+6, n²) — the six faces of the die, clipped at the final square. That's the edge set; there's no adjacency list to build because the edges are implicit in the arithmetic.

The boustrophedon conversion is the only real work. Squares are numbered from the bottom-left, snaking upward: the bottom row goes left-to-right, the row above goes right-to-left, and so on. To read board[r][c] for a label we invert that numbering. Let q = (label-1) / n and r = (label-1) % n. The row from the top is n-1-q (because numbering starts at the bottom). Whether the column runs forward or backward depends on the parity of q: even rows-from-bottom go left-to-right (col = r), odd ones go right-to-left (col = n-1-r). Getting this parity wrong is the single most common bug, so isolate it in a helper and test it on a couple of labels.

Forced jumps, applied once. After computing the landing square next, peek at its board value. If it's -1, you simply stop there. Otherwise a snake or ladder forces you to board[r][c] — and that's the square you actually occupy. Crucially, you do not chain: even if the destination of a ladder itself holds another snake, you take exactly one jump per move. Mark that final destination visited and enqueue it, never the intermediate roll square.

Counting moves by layers. We process the queue one full layer at a time, incrementing moves after each layer drains. Because BFS reaches every node by its shortest distance, the layer index at which n² is first dequeued is precisely the minimum number of moves. If the queue empties first, n² is unreachable and we return -1.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

board = [[-1,-1],[-1,3]] (n = 2, n² = 4)

Interactive diagram

BFS layers as move counts

moves=0

Active call / nodeSupporting contextReturned stateNot active

Each BFS layer is one dice roll; the layer where n² appears is the answer.

Final result1

C · Code with teaching comments

solution.javaJava

BFS Layer-by-Layer (Optimal) — optimal

6 teaching notes

1
public int snakesAndLadders(int[][] board) {
2
    int n = board.length;
3
    boolean[] visited = new boolean[n * n + 1];
4
    Queue<Integer> queue = new LinkedList<>();
5
    queue.offer(1);
6
    visited[1] = true;
7
    int moves = 0;
8
    while (!queue.isEmpty()) {
9
        int size = queue.size();
10
        for (int i = 0; i < size; i++) {
11
            int label = queue.poll();
12
            if (label == n * n) {
13
                return moves;
14
            }
15
            for (int next = label + 1; next <= Math.min(label + 6, n * n); next++) {
16
                int[] rc = toCoord(next, n);
17
                int dest = board[rc[0]][rc[1]];
18
                int target = (dest == -1) ? next : dest; // forced jump, once
19
                if (!visited[target]) {
20
                    visited[target] = true; // mark on enqueue
21
                    queue.offer(target);
22
                }
23
            }
24
        }
25
        moves++;
26
    }
27
    return -1;
28
}
29
 
30
private int[] toCoord(int label, int n) {
31
    int quotient = (label - 1) / n;
32
    int remainder = (label - 1) % n;
33
    int row = n - 1 - quotient; // numbering starts at the bottom
34
    // Boustrophedon: even rows-from-bottom go left-to-right, odd ones reverse.
35
    int col = (quotient % 2 == 0) ? remainder : n - 1 - remainder;
36
    return new int[]{row, col};
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO(n²) timeO(n²) spaceOpen the invariant and proofExplore the proof

The hard part of this 'graph' problem isn't the graph algorithm — it's the indexing. Once you trust 'unweighted shortest path ⇒ BFS', the entire challenge collapses to one correct coordinate-conversion helper. Naming that split out loud ('BFS is trivial; let me get the boustrophedon math right') is exactly the structured thinking interviewers reward.

ComplexityO(n²) time, O(n²) space — There are n² squares; each is enqueued at most once (visited guard) and explores ≤ 6 neighbours, so the work is O(6·n²) = O(n²). The visited array and queue are O(n²) space.

E · Edge cases and pitfalls7n = 2, reachable in one roll — Square 1 can roll directly to n²=4 → answer 1.Explore edge cases

Edge cases handled

n = 2, reachable in one rollSquare 1 can roll directly to n²=4 → answer 1.
board with self-defeating snakes (example 3)Goal never enters the queue; the loop ends and returns -1.
ladder whose destination has another ladderOnly the first jump is taken — the second is NOT chained, per the rules.

Pitfalls

Using DFS — finds a path, not the shortest one.
Chaining snakes/ladders instead of applying exactly one forced jump per move.
Marking visited by the rolled square instead of the final destination, allowing duplicates.
Off-by-one in the boustrophedon row/column conversion (forgetting numbering starts at the bottom).

03.2

Approach 2 of 2

BFS with a Distance Array

TimeO(n²)SpaceO(n²)

Offer as a tidy alternative that stores each square's distance instead of counting layers — handy if the interviewer also wants the distance to every square.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of processing whole layers, store dist[square] = fewest moves to reach it, initialised to -1 (unseen).

2Hint 2Explore hint

When you pop a square, its dist is final; set each unseen neighbour's dist to dist[current] + 1 and enqueue.

3Hint 3Explore hint

dist[n²] is the answer (still -1 if unreachable). The visited check is simply 'dist == -1'.

A · Core idea

This is the same BFS with different bookkeeping — instead of an explicit layer loop, each node carries its own distance.

Distance replaces the layer counter. We keep an array dist where dist[s] is the minimum moves to reach square s, initialised to -1 to mean 'not yet seen'. dist[1] = 0 seeds the start. When we dequeue square label, BFS guarantees dist[label] is already its shortest distance, so any newly discovered neighbour target gets dist[target] = dist[label] + 1.

The dist array is also the visited set. A square is unvisited exactly when its distance is still -1. Checking dist[target] == -1 before relaxing both prevents re-enqueueing and preserves the shortest distance already recorded — because in unweighted BFS the first assignment is always the smallest. This folds two data structures (visited + distance) into one.

Reading off the answer. We can return early the moment we set or pop n², but it's just as clean to run BFS to completion and return dist[n²] — which is -1 automatically if the goal was never reached. That uniform handling of the unreachable case is the small ergonomic win of this version.

Same forced-jump logic. The coordinate conversion and the single-jump snake/ladder rule are identical to the layer version; only the move-counting mechanism changes. Pick whichever you find less error-prone under pressure — many people prefer the distance array because it removes the inner 'for each node in this layer' loop and its off-by-one risks.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

board = [[-1,-1],[-1,3]] (n = 2)

pop 1 (dist 0)

rolls 2,3,4 unseen → dist=1 each, enqueue

Statedist[2]=dist[3]=dist[4]=1

Final result1

C · Code with teaching comments

Reference implementation previewpublic int snakesAndLadders(int[][] board) { int n = board.length; int[] dist = new int[n * n + 1]; Arrays.fill(dist, -1); dist[1] = 0;Explore the full code

solution.javaJava

BFS with a Distance Array — reference

4 teaching notes

1
public int snakesAndLadders(int[][] board) {
2
    int n = board.length;
3
    int[] dist = new int[n * n + 1];
4
    Arrays.fill(dist, -1);
5
    dist[1] = 0;
6
    Queue<Integer> queue = new LinkedList<>();
7
    queue.offer(1);
8
    while (!queue.isEmpty()) {
9
        int label = queue.poll();
10
        if (label == n * n) {
11
            return dist[label];
12
        }
13
        for (int next = label + 1; next <= Math.min(label + 6, n * n); next++) {
14
            int[] rc = toCoord(next, n);
15
            int dest = board[rc[0]][rc[1]];
16
            int target = (dest == -1) ? next : dest;
17
            if (dist[target] == -1) {
18
                dist[target] = dist[label] + 1;
19
                queue.offer(target);
20
            }
21
        }
22
    }
23
    // If never reached it stays -1, giving the unreachable answer for free.
24
    return dist[n * n];
25
}
26
 
27
private int[] toCoord(int label, int n) {
28
    int quotient = (label - 1) / n;
29
    int remainder = (label - 1) % n;
30
    int row = n - 1 - quotient;
31
    int col = (quotient % 2 == 0) ? remainder : n - 1 - remainder;
32
    return new int[]{row, col};
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n²) timeO(n²) spaceOpen the invariant and proofExplore the proof

Layer-counting and a distance array are two interchangeable ways to track BFS depth. The distance array shines when you need the distance to every node, not just the goal, and it elegantly returns -1 for unreachable targets with no special-casing.

ComplexityO(n²) time, O(n²) space — Same graph, same traversal: each square enqueued once, ≤ 6 neighbours each → O(n²) time. The dist array is O(n²) space and doubles as the visited marker.

E · Edge cases and pitfalls6unreachable goal — dist[n²] is never set, stays -1, returned at the end.Explore edge cases

Edge cases handled

unreachable goaldist[n²] is never set, stays -1, returned at the end.
goal reachable directlydist[n²] set to 1 on the first pop → returned as 1.
large n=20 board400 squares, ≤6 edges each — well within O(n²).

Pitfalls

Initialising dist to 0 instead of -1 — then the start can't be distinguished from unseen squares.
Updating dist for an already-seen square — corrupts the shortest distance.
Reusing the layer-loop AND the dist array together, double-counting moves.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int snakesAndLadders(int[][] board) { int n = board.length; boolean[] visited = new boolean[n * n + 1]; Queue<Integer> queue = new LinkedList<>(); queue.offer(1);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public int snakesAndLadders(int[][] board) {
    int n = board.length;
    boolean[] visited = new boolean[n * n + 1];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(1);
    visited[1] = true;
    int moves = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int label = queue.poll();
            if (label == n * n) {
                return moves;
            }
            for (int next = label + 1; next <= Math.min(label + 6, n * n); next++) {
                int[] rc = toCoord(next, n);
                int dest = board[rc[0]][rc[1]];
                int target = (dest == -1) ? next : dest; // forced jump, once
                if (!visited[target]) {
                    visited[target] = true; // mark on enqueue
                    queue.offer(target);
                }
            }
        }
        moves++;
    }
    return -1;
}

private int[] toCoord(int label, int n) {
    int quotient = (label - 1) / n;
    int remainder = (label - 1) % n;
    int row = n - 1 - quotient; // numbering starts at the bottom
    int col = (quotient % 2 == 0) ? remainder : n - 1 - remainder;
    return new int[]{row, col};
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Chaining snakes and ladders

A move is one dice roll plus at most one forced jump. If the landing square has a ladder, you take it once; you do NOT then follow a snake/ladder at that destination. Chaining computes wrong distances.

Explore the code comparison

Don't write this

r, c = to_coord(nxt)
while board[r][c] != -1:        # wrong: chains jumps
    nxt = board[r][c]
    r, c = to_coord(nxt)
target = nxt

Write this instead

r, c = to_coord(nxt)
dest = board[r][c]
target = nxt if dest == -1 else dest   # single forced jump

Wrong boustrophedon row/column math

Numbering starts at the bottom-left and alternates direction. Forgetting that rows count up from the bottom, or that odd rows reverse, maps labels to the wrong cell and reads the wrong board value.

Explore the code comparison

Don't write this

int row = label / n;                 // ignores bottom-up + 1-indexing
int col = label % n;                 // ignores alternating direction
int dest = board[row][col];

Write this instead

int quotient = (label - 1) / n;
int remainder = (label - 1) % n;
int row = n - 1 - quotient;
int col = (quotient % 2 == 0) ? remainder : n - 1 - remainder;
int dest = board[row][col];

Using DFS for a shortest-path question

DFS dives down one branch and may reach the goal via a long path first. Only BFS, exploring by increasing distance, guarantees the minimum number of moves on an unweighted graph.

Explore the code comparison

Don't write this

def dfs(square, moves):
    if square == n * n:
        return moves            # not necessarily minimal
    # explore one neighbour deeply...

Write this instead

queue = deque([1])
moves = 0
while queue:
    for _ in range(len(queue)):
        square = queue.popleft()
        if square == n * n:
            return moves        # BFS ⇒ first arrival is shortest
    moves += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Shortest path on an unweighted implicit graph → BFS

Code pattern to memorize

queue = [1]; visited = {1}; moves = 0
while queue:
    for each node in this layer:
        if node == n*n: return moves
        for next in node+1 .. node+6:
            dest = board value if snake/ladder else next
            if dest unseen: visit + enqueue
    moves += 1
return -1

Rules to remember

1Each move = a dice roll, so every edge has weight 1 → BFS gives the shortest path (not DFS, not Dijkstra).
2Flatten 2D → 1D with boustrophedon numbering: rows alternate left-to-right and right-to-left, starting bottom-left.
3From square x you can go to x+1 … x+6; a snake/ladder at the landing square is a forced jump (apply once, don't chain).
4Mark a square visited when you enqueue it, keyed by its final destination, not the intermediate roll square.
5Process the queue one layer at a time and increment moves per layer; the layer index is the distance.

Use this pattern when

Fewest steps / minimum moves on an unweighted board or grid
Shortest transformation where each step has equal cost
Implicit graph: nodes are states, edges are the legal moves between them
Board / tile games asking 'minimum dice rolls / jumps to finish'

Choose another pattern when

Edges have different costs → Dijkstra, not plain BFS
You need ALL paths or the longest path → DFS / DP, not BFS
Negative weights appear → Bellman-Ford

Interview takeaway

Snakes and Ladders is BFS hiding behind a board game. The only real work is the index math to flatten the boustrophedon grid; once squares are numbered 1…n², it's the same shortest-path-on-unweighted-graph BFS as Word Ladder, Open the Lock, and Minimum Genetic Mutation.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBFS for shortest path on an unweighted implicit graph. Squares are nodes, dice rolls and forced jumps are equal-cost edges. Same family as Word Ladder, Open the Lock, Minimum Genetic Mutation, and Shortest Path in Binary Matrix — the recurring tell is 'minimum number of moves/steps with equal cost'.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Word Ladder
Same BFS shortest-path idea where nodes are words and edges are one-letter changes.
Open the Lock
Coming soon
BFS over lock states; each wheel turn is one unweighted edge, with 'deadends' as blocked nodes.
Shortest Path in Binary Matrix
Coming soon
BFS on a grid with 8-directional moves — minimum steps from corner to corner.
Minimum Genetic Mutation
BFS over gene strings; each single-character mutation against a bank is one move.

Same pattern

←

Minimum Genetic Mutation

Continue · Next problem

Surrounded Regions

mediumGraphsLC #909Sometimes asked

Snakes and Ladders

LCPractice

Graphs · 11 of 34 · 11 min

Return the least number of moves required to reach the square `n²`. If it is not possible to reach the square, return -1.

In plain English

Examples

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
Note: From square 1 a roll to 2 takes the ladder to 15. From 15 reach 17, then 13 via the snake, then to 35 via the ladder, finishing at 36 (n²) in 4 moves.

Example 2

Input: board = [[-1,-1],[-1,3]]
Output: 1
Note: n=2 so n²=4. Square 1 is board[1][0]. A single roll can reach square 4 directly, so the answer is 1.

Example 3

Input: board = [[1,1,-1],[1,1,1],[-1,1,1]]
Output: -1
Note: Snakes/ladders that point back keep you from ever reaching the final square — BFS empties the queue and returns -1.

Constraints

n == board.length == board[i].length
2 ≤ n ≤ 20
grid[i][j] is either -1 or in the range [1, n²]
The squares labeled 1 and n² do not have any ladders or snakes

Clarifying questions4First question: How exactly are the squares numbered?Explore questions

Q1.How exactly are the squares numbered?
Boustrophedon: square 1 is the bottom-left cell, the bottom row runs left-to-right, the next row up runs right-to-left, and so on. I'll write a helper to convert a label back to (row, col).
Q2.If I land on a ladder/snake, do I roll again or chain to another ladder?
Neither — the jump is forced and applied exactly once. You do not roll from the landing square, and a destination that itself holds a snake/ladder is not chained.
Q3.Since every move is one dice roll, are all edges equal weight?
Yes — each move costs 1 regardless of where the die or a ladder takes you. Equal weights mean BFS gives the shortest path; Dijkstra would be overkill.
Q4.What if the end square is unreachable?
Return -1. BFS detects this when the queue empties before n² is ever dequeued.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Using DFS (which finds *a* path, not the shortest), chaining snakes/ladders (a jump should be applied only once), or getting the boustrophedon row/column conversion wrong.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	BFS Layer-by-Layer (Optimal)Optimal	`O(n²)`	`O(n²)`	Lead with this. Phrase it as 'minimum moves on an unweighted graph is textbook BFS — the only twist is the snake-style numbering'.	Read
2	BFS with a Distance Array	`O(n²)`	`O(n²)`	Offer as a tidy alternative that stores each square's distance instead of counting layers — handy if the interviewer also wants the distance to every square.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

BFS Layer-by-Layer (Optimal)

TimeO(n²)SpaceO(n²)

Lead with this. Phrase it as 'minimum moves on an unweighted graph is textbook BFS — the only twist is the snake-style numbering'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each square 1…n² is a node. From square x you can roll to x+1 … x+6, so each node has up to 6 outgoing edges, every edge costing one move.

2Hint 2Explore hint

Equal edge cost ⇒ BFS finds the fewest moves. Process the queue one layer at a time and the layer number is the move count.

3Hint 3Explore hint

The fiddly part is mapping a label back to (row, col): rows are numbered bottom-up, and alternate direction. Write a helper, and remember a snake/ladder is a single forced jump.

A · Core idea

Strip away the board-game dressing and this is the most standard shortest-path problem there is.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

board = [[-1,-1],[-1,3]] (n = 2, n² = 4)

Interactive diagram

BFS layers as move counts

moves=0

Active call / nodeSupporting contextReturned stateNot active

Each BFS layer is one dice roll; the layer where n² appears is the answer.

Final result1

C · Code with teaching comments

solution.javaJava

BFS Layer-by-Layer (Optimal) — optimal

6 teaching notes

1
public int snakesAndLadders(int[][] board) {
2
    int n = board.length;
3
    boolean[] visited = new boolean[n * n + 1];
4
    Queue<Integer> queue = new LinkedList<>();
5
    queue.offer(1);
6
    visited[1] = true;
7
    int moves = 0;
8
    while (!queue.isEmpty()) {
9
        int size = queue.size();
10
        for (int i = 0; i < size; i++) {
11
            int label = queue.poll();
12
            if (label == n * n) {
13
                return moves;
14
            }
15
            for (int next = label + 1; next <= Math.min(label + 6, n * n); next++) {
16
                int[] rc = toCoord(next, n);
17
                int dest = board[rc[0]][rc[1]];
18
                int target = (dest == -1) ? next : dest; // forced jump, once
19
                if (!visited[target]) {
20
                    visited[target] = true; // mark on enqueue
21
                    queue.offer(target);
22
                }
23
            }
24
        }
25
        moves++;
26
    }
27
    return -1;
28
}
29
 
30
private int[] toCoord(int label, int n) {
31
    int quotient = (label - 1) / n;
32
    int remainder = (label - 1) % n;
33
    int row = n - 1 - quotient; // numbering starts at the bottom
34
    // Boustrophedon: even rows-from-bottom go left-to-right, odd ones reverse.
35
    int col = (quotient % 2 == 0) ? remainder : n - 1 - remainder;
36
    return new int[]{row, col};
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO(n²) timeO(n²) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7n = 2, reachable in one roll — Square 1 can roll directly to n²=4 → answer 1.Explore edge cases

Edge cases handled

n = 2, reachable in one rollSquare 1 can roll directly to n²=4 → answer 1.
board with self-defeating snakes (example 3)Goal never enters the queue; the loop ends and returns -1.
ladder whose destination has another ladderOnly the first jump is taken — the second is NOT chained, per the rules.

Pitfalls

Using DFS — finds a path, not the shortest one.
Chaining snakes/ladders instead of applying exactly one forced jump per move.
Marking visited by the rolled square instead of the final destination, allowing duplicates.
Off-by-one in the boustrophedon row/column conversion (forgetting numbering starts at the bottom).

03.2

Approach 2 of 2

BFS with a Distance Array

TimeO(n²)SpaceO(n²)

Offer as a tidy alternative that stores each square's distance instead of counting layers — handy if the interviewer also wants the distance to every square.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of processing whole layers, store dist[square] = fewest moves to reach it, initialised to -1 (unseen).

2Hint 2Explore hint

When you pop a square, its dist is final; set each unseen neighbour's dist to dist[current] + 1 and enqueue.

3Hint 3Explore hint

dist[n²] is the answer (still -1 if unreachable). The visited check is simply 'dist == -1'.

A · Core idea

This is the same BFS with different bookkeeping — instead of an explicit layer loop, each node carries its own distance.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

board = [[-1,-1],[-1,3]] (n = 2)

pop 1 (dist 0)

rolls 2,3,4 unseen → dist=1 each, enqueue

Statedist[2]=dist[3]=dist[4]=1

Final result1

C · Code with teaching comments

Reference implementation previewpublic int snakesAndLadders(int[][] board) { int n = board.length; int[] dist = new int[n * n + 1]; Arrays.fill(dist, -1); dist[1] = 0;Explore the full code

solution.javaJava

BFS with a Distance Array — reference

4 teaching notes

1
public int snakesAndLadders(int[][] board) {
2
    int n = board.length;
3
    int[] dist = new int[n * n + 1];
4
    Arrays.fill(dist, -1);
5
    dist[1] = 0;
6
    Queue<Integer> queue = new LinkedList<>();
7
    queue.offer(1);
8
    while (!queue.isEmpty()) {
9
        int label = queue.poll();
10
        if (label == n * n) {
11
            return dist[label];
12
        }
13
        for (int next = label + 1; next <= Math.min(label + 6, n * n); next++) {
14
            int[] rc = toCoord(next, n);
15
            int dest = board[rc[0]][rc[1]];
16
            int target = (dest == -1) ? next : dest;
17
            if (dist[target] == -1) {
18
                dist[target] = dist[label] + 1;
19
                queue.offer(target);
20
            }
21
        }
22
    }
23
    // If never reached it stays -1, giving the unreachable answer for free.
24
    return dist[n * n];
25
}
26
 
27
private int[] toCoord(int label, int n) {
28
    int quotient = (label - 1) / n;
29
    int remainder = (label - 1) % n;
30
    int row = n - 1 - quotient;
31
    int col = (quotient % 2 == 0) ? remainder : n - 1 - remainder;
32
    return new int[]{row, col};
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n²) timeO(n²) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6unreachable goal — dist[n²] is never set, stays -1, returned at the end.Explore edge cases

Edge cases handled

unreachable goaldist[n²] is never set, stays -1, returned at the end.
goal reachable directlydist[n²] set to 1 on the first pop → returned as 1.
large n=20 board400 squares, ≤6 edges each — well within O(n²).

Pitfalls

Initialising dist to 0 instead of -1 — then the start can't be distinguished from unseen squares.
Updating dist for an already-seen square — corrupts the shortest distance.
Reusing the layer-loop AND the dist array together, double-counting moves.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Chaining snakes and ladders

Explore the code comparison

Don't write this

r, c = to_coord(nxt)
while board[r][c] != -1:        # wrong: chains jumps
    nxt = board[r][c]
    r, c = to_coord(nxt)
target = nxt

Write this instead

r, c = to_coord(nxt)
dest = board[r][c]
target = nxt if dest == -1 else dest   # single forced jump

Wrong boustrophedon row/column math

Numbering starts at the bottom-left and alternates direction. Forgetting that rows count up from the bottom, or that odd rows reverse, maps labels to the wrong cell and reads the wrong board value.

Explore the code comparison

Don't write this

int row = label / n;                 // ignores bottom-up + 1-indexing
int col = label % n;                 // ignores alternating direction
int dest = board[row][col];

Write this instead

int quotient = (label - 1) / n;
int remainder = (label - 1) % n;
int row = n - 1 - quotient;
int col = (quotient % 2 == 0) ? remainder : n - 1 - remainder;
int dest = board[row][col];

Using DFS for a shortest-path question

DFS dives down one branch and may reach the goal via a long path first. Only BFS, exploring by increasing distance, guarantees the minimum number of moves on an unweighted graph.

Explore the code comparison

Don't write this

def dfs(square, moves):
    if square == n * n:
        return moves            # not necessarily minimal
    # explore one neighbour deeply...

Write this instead

queue = deque([1])
moves = 0
while queue:
    for _ in range(len(queue)):
        square = queue.popleft()
        if square == n * n:
            return moves        # BFS ⇒ first arrival is shortest
    moves += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Shortest path on an unweighted implicit graph → BFS

Code pattern to memorize

queue = [1]; visited = {1}; moves = 0
while queue:
    for each node in this layer:
        if node == n*n: return moves
        for next in node+1 .. node+6:
            dest = board value if snake/ladder else next
            if dest unseen: visit + enqueue
    moves += 1
return -1

Rules to remember

1Each move = a dice roll, so every edge has weight 1 → BFS gives the shortest path (not DFS, not Dijkstra).
2Flatten 2D → 1D with boustrophedon numbering: rows alternate left-to-right and right-to-left, starting bottom-left.
3From square x you can go to x+1 … x+6; a snake/ladder at the landing square is a forced jump (apply once, don't chain).
4Mark a square visited when you enqueue it, keyed by its final destination, not the intermediate roll square.
5Process the queue one layer at a time and increment moves per layer; the layer index is the distance.

Use this pattern when

Fewest steps / minimum moves on an unweighted board or grid
Shortest transformation where each step has equal cost
Implicit graph: nodes are states, edges are the legal moves between them
Board / tile games asking 'minimum dice rolls / jumps to finish'

Choose another pattern when

Edges have different costs → Dijkstra, not plain BFS
You need ALL paths or the longest path → DFS / DP, not BFS
Negative weights appear → Bellman-Ford

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Word Ladder
Same BFS shortest-path idea where nodes are words and edges are one-letter changes.
Open the Lock
Coming soon
BFS over lock states; each wheel turn is one unweighted edge, with 'deadends' as blocked nodes.
Shortest Path in Binary Matrix
Coming soon
BFS on a grid with 8-directional moves — minimum steps from corner to corner.
Minimum Genetic Mutation
BFS over gene strings; each single-character mutation against a bank is one move.

Same pattern

←

Minimum Genetic Mutation

Continue · Next problem

Surrounded Regions