Snakes and Ladders

Medium
471.

Snakes and Ladders

Snakes and Ladders is a medium coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google, Microsoft and Zomato interviews.

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 <= 8
  • board[i].length == board.length
  • board[i][j] is -1 or in the range [1, n²]
  • Squares 1 and n² never carry a snake or ladder.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} board
 * @return {number}
 */
var snakesAndLadders = function(board) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 8
  • board[i].length == board.length
  • board[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

  1. Hint 1

    Every move costs one, so breadth-first search over the squares finds the minimum.

  2. Hint 2

    The trickiest part is the numbering — write a helper that maps a square number to its row and column.

  3. 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

  1. value_at(square) computes row = n - 1 - (square-1) // n and flips the column on alternate rows.
  2. BFS from square 1; for each die roll 1..6, land, apply any redirect, enqueue if unseen.
  3. 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 -1

Java

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