What is the brute force approach and complexity for Snakes and Ladders?

Repeat full passes over the squares, shortening roll counts, until a whole pass changes nothing with time complexity O(N⁴) and space complexity O(N²).

What is the optimal approach and complexity for Snakes and Ladders?

BFS from square 1: each roll is one edge, and at most one snake or ladder is taken per roll with optimal time complexity O(N²) and space complexity O(N²).

Snakes and Ladders

Q: How do you identify the pattern for Snakes and Ladders?

Look for key signals in the prompt: "fewest rolls" indicates Every roll costs 1, so the answer is a shortest-path count. BFS by rolls gives it directly.; "next 6 squares" indicates From square s there are up to 6 edges, to s + 1 … s + 6. The graph lies along the square numbers, not on the grid.; "snake or ladder" indicates A jump happens inside a roll: the roll ends on the jump's destination. Only one jump counts per roll..

Medium·LeetCode #909 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given an n × n board. Its squares are numbered from 1 to n² in a snake-like order: the bottom row goes left to right, the row above it goes right to left, and so on. You start on square 1.

Each roll moves you to any one of the next 6 squares: from square s you can land on s + 1, …, s + 6, but never past square n².

If the square you land on has a snake or a ladder, you must take it to its destination. You take at most one snake or ladder per roll. If that destination is the start of another snake or ladder, you stay where you are and do not follow it.

Return the fewest rolls needed to reach square n². If it cannot be reached, return -1.

Input

board, an n × n grid. Row 0 is the top row of the grid. board[r][c] is -1 if that square has no snake or ladder. Otherwise it is the square the snake or ladder sends you to.

Output

The fewest number of rolls to reach square n², or -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

Roll 1 goes from 1 to 2 and climbs the ladder to 15. Roll 2 goes from 15 to 17 and slides down the snake to 13. Roll 3 goes from 13 to 14 and climbs the ladder to 35. Roll 4 goes from 35 to 36, the last square.

Example 2

Input: board = [[-1,-1],[-1,3]]

Output: 1

On a 2 × 2 board, a roll of 3 from square 1 lands on square 4, the last square.

Example 3

Input: board = [[-1,-1,-1,-1],[14,-1,-1,-1],[-1,-1,-1,-1],[-1,9,-1,-1]]

Output: 3

Roll 1 goes from 1 to 2, which is a ladder to 9. You stop on 9, and its ladder to 14 is not taken in the same roll. Roll 2 goes from 9 to 15. Roll 3 goes from 15 to 16. Three rolls.

Constraints

• The board is n × n, with 2 ≤ n ≤ 20.
• Each cell holds -1 or a square number from 1 to n².
• Squares 1 and n² never have a snake or ladder.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“fewest rolls”

→ Every roll costs 1, so the answer is a shortest-path count. BFS by rolls gives it directly.

“next 6 squares”

→ From square s there are up to 6 edges, to s + 1 … s + 6. The graph lies along the square numbers, not on the grid.

“snake or ladder”

→ A jump happens inside a roll: the roll ends on the jump's destination. Only one jump counts per roll.

Approach Complexity Ladder

Brute Force — relax every roll until nothing changesO(N⁴)O(N²)

Repeat full passes over the squares, shortening roll counts, until a whole pass changes nothing

Optimal — BFS over squares, one roll per edgeO(N²)O(N²)

BFS from square 1: each roll is one edge, and at most one snake or ladder is taken per roll

Brute Force Intuition

Give square 1 a roll count of 0 and every other square ∞. In each pass, look at every square and update the squares its rolls reach if that gives a smaller count. Keep making passes until a whole pass changes nothing. Then every count is final.

Recognition rule for this sub-pattern:

Nodes are states (lock codes, words, board squares). Generate neighbours on the fly.

Remember this · Graph BFS / DFS

Trigger

Grid of cells, islands, regions, "minimum steps", transformations between states, connected components.

Think

What is a node, what is an edge, and do I need the shortest path or just reachability?

Key question

How do I mark visited so I never process a node twice?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track

C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track

Open the Lock The Maze