#909 Snakes and Ladders

frequently reported atAmazon Google Microsoft Bloomberg Meta

the problem

In plain words

An n × n board numbers its squares 1 to n², starting at the bottom-left and zig-zagging upwards: left → right on the bottom row, right → left on the next, and so on. You start on square 1. Each roll moves you 1 to 6 squares forward (never past n²). If you land on a square whose board[r][c] isn't -1, you must jump to square board[r][c] — a snake or a ladder — but only once per roll, even if that square starts another jump. Return the fewest rolls to reach square n², or -1 if it can't be done.

in 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]]

out 4

Roll to 2 → ladder to 15. Roll to 17 → snake to 13. Roll to 14 → ladder to 35. Roll to 36.

in board = [[-1,-1],[-1,3]]

out 1

Roll a 3 and land on square 4, the last square. (Square 2 has a ladder to 3, but that doesn't help.)

n == board.length == board[i].length
2 ≤ n ≤ 20
board[i][j] is -1 or in [1, n²]
Squares 1 and n² have no snake or ladder

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBFS shortest path (unweighted)

Squares are vertices; a roll is an edge to up to 6 squares (after taking any snake or ladder). Every roll costs 1, so the fewest rolls is a BFS from square 1. The only fiddly part is turning a square number into (row, col).

solutions

From brute force to optimal

Bellman–Ford style: keep a best-known roll count per square and keep improving it from every reachable square until a full pass changes nothing.

dist[1] = 0, others ∞.
Repeat: for every square with a finite dist, for each roll 1..6, follow any jump and lower dist[dest] if dist + 1 is smaller.
Stop after a pass with no change; answer dist[n²] or -1.

timeO(n⁴)

Each pass is n² squares × 6 rolls, and it can take up to n² passes for values to settle.

spaceO(n²)

One dist entry per square.

javajava.util.*

1class Solution {2    /** Bellman-Ford style: keep improving dist[] with every possible roll until nothing changes. */3    public int snakesAndLadders(int[][] board) {4        int n = board.length, last = n * n;5        int[] dist = new int[last + 1];6        Arrays.fill(dist, Integer.MAX_VALUE);7        dist[1] = 0;8        boolean changed = true;9        while (changed) { // at most n² rounds: each round fixes at least one more square10            changed = false;11            for (int cur = 1; cur < last; cur++) {12                if (dist[cur] == Integer.MAX_VALUE) continue;13                for (int next = cur + 1; next <= Math.min(cur + 6, last); next++) {14                    int[] rc = cell(next, n);15                    int dest = board[rc[0]][rc[1]] == -1 ? next : board[rc[0]][rc[1]];16                    if (dist[cur] + 1 < dist[dest]) {17                        dist[dest] = dist[cur] + 1;18                        changed = true;19                    }20                }21            }22        }23        return dist[last] == Integer.MAX_VALUE ? -1 : dist[last];24    }25 26    private int[] cell(int label, int n) {27        int fromBottom = (label - 1) / n, offset = (label - 1) % n;28        int col = fromBottom % 2 == 0 ? offset : n - 1 - offset;29        return new int[] {n - 1 - fromBottom, col};30    }31}

BFS from square 1. For each of the 6 rolls, convert the target square to (row, col), take its jump if any, and enqueue the destination if it is new.

rolls[1] = 0; queue = [1].
Poll cur; if cur == n², return rolls[cur].
For next in cur+1..min(cur+6, n²): dest = board at next == -1 ? next : that value.
If dest is unvisited: rolls[dest] = rolls[cur] + 1, enqueue it.

timeO(n²)

Each of the n² squares is enqueued at most once and tries 6 rolls.

spaceO(n²)

The rolls array and the queue.

javajava.util.*

1class Solution {2    /** Squares are vertices; one roll is one edge. BFS gives the fewest rolls. */3    public int snakesAndLadders(int[][] board) {4        int n = board.length, last = n * n;5        int[] rolls = new int[last + 1]; // rolls needed to stand on each square; -1 = not reached6        Arrays.fill(rolls, -1);7        Deque<Integer> queue = new ArrayDeque<>();8        rolls[1] = 0;9        queue.offer(1);10        while (!queue.isEmpty()) {11            int cur = queue.poll();12            if (cur == last) return rolls[cur];13            for (int next = cur + 1; next <= Math.min(cur + 6, last); next++) {14                int[] rc = cell(next, n);15                int dest = board[rc[0]][rc[1]] == -1 ? next : board[rc[0]][rc[1]]; // take at most one jump16                if (rolls[dest] != -1) continue;17                rolls[dest] = rolls[cur] + 1;18                queue.offer(dest);19            }20        }21        return -1;22    }23 24    /** Square label (1..n²) → {row, col}. Row 0 is the TOP; numbering starts bottom-left and zig-zags. */25    private int[] cell(int label, int n) {26        int fromBottom = (label - 1) / n, offset = (label - 1) % n;27        int col = fromBottom % 2 == 0 ? offset : n - 1 - offset; // even rows from the bottom go left → right28        return new int[] {n - 1 - fromBottom, col};29    }30}

in the room

How to say it in the interview

talk track

Say: "Fewest rolls, every roll costs 1 → BFS over squares 1..n²."
Write the label → (row, col) helper first and test it on a 2×2 and a 3×3 board out loud.
Mark the destination after the jump as visited, not the square you rolled onto.

traps

Getting the zig-zag wrong: row from the bottom = (s − 1) / n; on odd rows from the bottom the column runs right → left.
Following a second jump when a ladder ends on another snake or ladder — only one jump per roll.
Marking the rolled-onto square visited instead of the jump destination — you can block a square you never actually stand on.

what they ask next

Follow-ups

Return the actual sequence of rolls?

Store each square's parent when you first reach it, then walk back from n² to 1.

What if a die had k faces?

Same BFS with k edges per square: O(n² · k).

before you submit

Edge cases to test

A ladder whose top starts another ladder — take only the first jump.
Snakes cover every square you can roll to → -1.
A ladder from square 2 straight to n² → 1 roll.
A plain 20 × 20 board → ⌈399 / 6⌉ = 67 rolls.

practise next