Imagine you're navigating a city where each intersection tells you how many blocks you can jump forward. Can you reach the final destination? What's the fewest number of jumps needed? Now imagine the city has snakes (they send you backward) and ladders (they catapult you forward). And what if the city has secret tunnels that create infinite loops?
These aren't just party games — they're real problem-solving frameworks.Jump games teach you the fundamentals of reachability, BFS on sequences, and greedy optimization. Network games extend these ideas to graphs with cycles, DAGs, and complex connectivity patterns.
By the end of this article, you'll have a mental toolkit for:
Deciding between greedy, BFS, or DP for reachability problems
Modeling board games as graph traversal
Detecting cycles in functional graphs (single outgoing edge per node)
Counting paths efficiently in directed acyclic graphs
Tip
💡 The Key Insight: ALL these problems reduce to graph traversal at their core. The "jump" is just an edge to a range of indices. The "snake" is a weighted teleport. The "mad city" is a functional graph with cycles. Once you see the graph, the solution is clear.
1. Jump Game I — Greedy Reachability
Problem: You are given an integer array nums. You are initially positioned at the first index. Each element nums[i]represents your maximum jump length from that position. Return trueif you can reach the last index, or false otherwise.
Note
🎯 Real-World Analogy: Imagine you're playing a board game where each square tells you the MAXIMUM number of squares you can advance. You land on square 2 — you can move 1 or 2 steps forward. You land on square 0 — you're stuck. The question: "Is there any path to the finish line?" You don't need the exact path, just whether it's possible! That's Jump Game I.
🤔 Think About It — The "What's the Furthest I Can Reach?" Pattern
This is the classic "choose/not-choose" decision applied to reachability:
This is the GREEDY approach: instead of exploring all paths, we simply track the furthest index we could possibly reach as we scan left to right. If at any point we're at an index beyond our maximum reach, we're stuck — return false.
Tech DOSE — Edge Cases & Gotchas
Edge Case 1: Single Element Array
If nums.length === 1, we're ALREADY at the last index. Return true regardless of the value. You don't need to jump.
Edge Case 2: Zero at Start
If nums[0] === 0 and length > 1, you can't move at all. Return false. The greedy check handles this: maxReach = 0, i=1 > 0 → stuck.
Edge Case 3: Zero in the Middle
A zero doesn't always mean stuck. If maxReach is already beyond that index, we can skip over it. Example: [3, 2, 0, 0, 4] — at i=0 we can reach up to index 3, so we can skip past the zeros at i=2,3.
Edge Case 4: Large Jumps
Values can be very large (up to 10^5). The greedy algorithm handles this in O(n) time regardless of jump magnitude — we just compute i + nums[i]and take max.
Solution
Key Insight
🔑 Why Greedy Works for Jump Game I: We don't need the MINIMUM number of jumps (that's Jump Game II). We only need to know IF the end is reachable. Since jumps are non-negative and we can choose any jump length up to nums[i], tracking the furthest reachable index at each step is sufficient. If a later index is reachable, it must be reachable from some earlier index within maxReach — and our loop visits all of them.
ProblemEmbed: jump-game
2. Jump Game II — Minimum BFS Jumps
Problem: Now we need the minimum number of jumpsto reach the last index. Each element represents your maximum jump length. It's guaranteed you CAN reach the last index (unlike Jump Game I).
Note
🎯 Real-World Analogy: Same board game, but now you're IN A RUSH. You need the FEWEST moves to reach the finish. You can see all the squares ahead (you have the full array). What's the optimal strategy? This is isomorphic to computing the shortest path in an unweighted graph where each node has edges to a range of successive nodes.
🤔 Think About It — The BFS "Levels" Pattern
This is the classic "At each level, I choose the best next reach" pattern:
The algorithm is often called "BFS-inspired greedy" because it mimics BFS level traversal without an explicit queue. We track:
jumps — number of jumps taken so far (BFS level)
currentEnd — the furthest index we can reach with current jump count
nextReach — the furthest index we CAN reach when we take one more jump
Tech DOSE — Edge Cases & Gotchas
Edge Case 1: Single Element
If n === 1, we're already at the end. Return 0 jumps.
Edge Case 2: First Jump Reaches End
If nums[0] >= n - 1, we can reach the end in 1 jump. The algorithm handles this: first iteration sets nextReach and then we immediately hit i === currentEnd (0), increment jumps to 1, set currentEnd = nextReach (>= n-1), and the loop stops because we process up to n-2. Actually, we stop at i = n-2, and since currentEnd >= n-1, we return jumps = 1. Correct!
Edge Case 3: All Ones
If every element is 1, we need exactly n - 1 jumps (one per index). The algorithm correctly computes this as each step extends currentEnd by 1.
Edge Case 4: Decreasing Reach
Example: [3, 1, 0, 1, 0]. At i=0, maxReach=3. At i=1, maxReach stays 3. At i=2, maxReach stays 3 (0+2=2). At i=3, maxReach = 4. We get to the end in 2 jumps (index 0 → index 3 → index 4).
Solution
Warning
⚠️ Common Mistake: Don't confuse Jump Game I and II algorithms. Jump Game I's greedy maxReach only tracks reachability. Jump Game II needs currentEnd and jumpscounters to measure the minimum number of BFS "layers". Using the Jump Game I algorithm for Jump Game II will tell you IF you can reach the end, but not the minimum jumps.
ProblemEmbed: jump-game-ii
3. Jump Game III — BFS on Index Graph
Problem: Given an array of non-negative integers arr, you are initially positioned at start index. When you are at index i, you can jump to i + arr[i]or i - arr[i]. Return true if you can reach any index with value 0.
Note
🎯 Real-World Analogy: You're in a strange labyrinth where each room has a number on the wall. You MUST move exactly that many rooms forward or backward. Your goal is to find ANY room with value 0 (the exit). This isn't about optimization — it's about reachability on a directed graph where each node has exactly TWO edges.
🤔 Think About It — The "Exactly k Steps" Constraint
Unlike Jump Game I where you can jump UP TO nums[i] steps, Jump Game III forces you to jump EXACTLY arr[i] steps either forward or backward. This changes everything:
BFS vs DFS Decision
Both BFS and DFS work for this problem. BFS is slightly better because it finds reachability without deep recursion (avoids stack overflow for large arrays). But DFS with explicit stack is also fine. The key is to track visited nodes to avoid infinite loops.
Tech DOSE — Edge Cases & Gotchas
Edge Case 1: Start is Already 0
If arr[start] === 0, return true immediately. You're already at a zero-valued index.
Edge Case 2: Out of Bounds
When computing i + arr[i] or i - arr[i], the result might be outside the array bounds. Skip any move that leads out of bounds.
Edge Case 3: Cycles
The graph can have cycles (e.g., [1, 1, 0], start=0 — 0→1, 1→0, 0→1... infinite loop). The visited set prevents re-processing.
Edge Case 4: Single Element Array
If arr.length === 1 and start=0, then if arr[0]===0 return true, else you can't move anywhere (jump leads out of bounds) → false.
Solution
Key Insight
🔑 BFS on Index Graph: Jump Game III transforms the array into a graph where each index has edges to exactly two neighbors (i + arr[i], i - arr[i]). The problem reduces to: "Is there a path from start to any node with value 0?" This is a standard graph reachability problem solvable with BFS or DFS.
ProblemEmbed: jump-game-iii
4. Snakes & Ladders — BFS on a Board
Problem: You are given an n × n board (numbered 1 to n² in a Boustrophedon pattern). Each cell contains either -1 (normal cell) or a number pointing to another cell (snake or ladder). You roll a 6-sided die each turn. Find the minimum number of moves to reach cell n², or -1 if impossible.
Note
🎯 Real-World Analogy: The classic childhood board game! You roll a die (1-6), your token moves forward. But watch out — land on a snake's head and you slide down! Land at the bottom of a ladder and you climb up! The board wraps in a serpentine pattern (alternating left-to-right, right-to-left). This is isomorphic to finding the shortest path in a directed graph with up to 6 outgoing edges per node.
🤔 Think About It — The Board to Graph Transformation
The first challenge is understanding the board numbering. The 10×10 board is numbered in a Boustrophedon (snake) pattern:
BFS on Board — Why BFS and not Dijkstra?
Each die roll costs exactly 1 move. All edges have equal weight. BFS finds the shortest path in an unweighted graph, which is exactly what we need. The only "twist" is that some edges teleport you (snakes/ladders), but each teleport still counts as just one move.
Tech DOSE — Edge Cases & Gotchas
Edge Case 1: Start at Cell 1
If cell 1 has a ladder, we immediately teleport. Our BFS must handle this by checking the destination before enqueuing.
Edge Case 2: Dice Roll Wraps Past n²
If a die roll takes us past n², we just stay at n²? Actually, standard rules say you need to land EXACTLY on n². If you overshoot, you don't move. But LeetCode allows any roll that lands on or past n² to count as reaching the end. Always clarify the rules.
Edge Case 3: Circular Snakes/Ladders
What if a ladder leads to a cell with a snake that sends you back? BFS handles this naturally — each cell is processed once (visited set), and teleportation happens instantly.
Edge Case 4: Impossible Board
If the board has cycles that prevent reaching n², BFS will exhaust all reachable cells and return -1.
Solution
Tip
⚡ Pro Tip: The board-to-position conversion is the trickiest part. Use the Boustrophedon formula carefully. Test with 2×2 or 3×3 boards first to verify your conversion is correct before running BFS.
ProblemEmbed: snakes-and-ladders
5. Mad City — Cycle Detection in Functional Graphs
Problem: There are n cities numbered 1 to n, connected by n one-way roads. Each city hasexactly one outgoing road to another city. This creates afunctional graph (each node has out-degree = 1). A subset of cities is "safe" if there exists a path that NEVER reaches a cycle. Determine which cities are safe.
Note
🎯 Real-World Analogy: Imagine a city where every intersection has a sign pointing to the NEXT intersection. There are no choices — you just follow the signs. Some roads lead to a giant roundabout (cycle) where you drive forever. Other roads lead to a dead end (sink) where traffic stops. "Safe" cities are those where you can eventually leave the system without getting stuck in the roundabout. This is exactly a functional graph problem.
🤔 Think About It — The Functional Graph Structure
A graph where every node has exactly one outgoing edge is called afunctional graph (or a "successor graph"). It has a very specific structure: the graph decomposes into a collection ofcycles with trees feeding into them.
Tech DOSE — Edge Cases & Gotchas
Edge Case 1: Self-Loop
If a city points to itself (next[i] === i), it's a cycle of length 1. That city is unsafe, and any city that leads to it is also unsafe.
Edge Case 2: All Nodes on One Cycle
If the entire graph is one big cycle (e.g., 1→2→3→...→n→1), then ALL nodes are on the cycle. No safe nodes exist.
Edge Case 3: Single Node Self-Loop
If n=1 and the node points to itself, it's a cycle → unsafe. Return empty list.
Edge Case 4: Multiple Disjoint Cycles
The graph can have multiple disconnected cycles, each with its own set of feeding trees. Process each component independently.
Solution
Warning
⚠️ Important: "Safe node" definition varies by problem. In some versions, a node is safe if you CAN reach a cycle (infinite play). In others, a node is safe if you can AVOID cycles forever. Always read the problem statement carefully. The Mad City problem typically asks: which cities are SAFE, where safe means you can eventually leave the city system (not trapped in a cycle).
ProblemEmbed: mad-city
6. Game Routes — Counting Paths in a DAG
Problem: Given a directed acyclic graph (DAG) with n nodes (numbered 1 to n) and m edges, count the number of distinct paths fromnode 1 to node n. Since the answer can be large, return it modulo 10⁹ + 7.
Note
🎯 Real-World Analogy: You're planning a road trip from city 1 to city n. There are one-way roads between cities, and you want to count how many possible routes exist. The graph has no cycles (it's a DAG), so the number of paths is finite. This is a classic DP-on-DAG problem that appears in CSES, Codeforces, and as a building block for more complex graph problems.
🤔 Think About It — The DP on DAG Pattern
When you need to count paths in a DAG, the natural approach is dynamic programming processed in topological order:
Tech DOSE — Edge Cases & Gotchas
Edge Case 1: No Path Exists
If node n is unreachable from node 1, dp[1] will remain 0 (initial value). The DP handles this automatically.
Edge Case 2: Self-Loops
The problem says DAG — there should be NO cycles. If the input contains a cycle, the DP would have infinite paths. The problem guarantees a DAG, but in practice you might want to detect cycles first.
Edge Case 3: Large Answers
The number of paths can be exponential. Always use modulo 10⁹ + 7 and a 64-bit integer type (or BigInt in JavaScript).
Edge Case 4: Single Node
If n=1, there's exactly 1 path (do nothing). The DP should return 1.
Solution
Key Insight
🔑 DP on DAG Pattern: Counting paths in a DAG is a fundamental pattern that extends to many problems: counting ways, finding longest/shortest paths, and even computing probabilities in probabilistic DAGs. The key insight: topological order guarantees that when processing node u, all its predecessors have already contributed to dp[u]. For "paths from source to target," we process forward from source; for "paths from any node to target," we process in reverse topological order.
ProblemEmbed: game-routes
🎯 Interview Cheat Sheet
Key Insight
Q1: When do I use Greedy vs BFS vs DP for reachability? Greedy: If the problem says "can you reach the end" with flexible jump lengths (Jump Game I) — track maxReach left to right. BFS: If you need MINIMUM steps on an unweighted graph (Jump Game II, Snakes & Ladders) — BFS levels = jump counts. DFS/DP: If the graph has weighted edges or you need to count paths (Game Routes) — topological DP or memoized DFS.
Key Insight
Q2: How do I recognize a functional graph problem? Keywords: "exactly one outgoing edge", "each node points to another node", "determine fate" (safe/unsafe, eventual cycle). The graph always decomposes into cycles with trees feeding in. Use topological removal or 3-color DFS.
Key Insight
Q3: What's the Boustrophedon conversion for Snakes & Ladders? The board is numbered in a serpentine (snake) pattern. Key formula: row index from the bottom = n - 1 - Math.floor((cell - 1) / n). Column depends on row parity: even rows go left→right, odd rows go right→left.
Key Insight
Q4: How do I count paths in a graph that might have cycles? If the graph has cycles, the number of paths is INFINITE (you can loop forever). For finite path counts, the graph MUST be a DAG. If the problem doesn't guarantee a DAG, check for cycles first with DFS topological sort or detect if any back edge exists.
Key Insight
Q5: Jump Game I vs II — what's the difference in algorithm? Jump Game I: Just track maxReach. When maxReach >= last index → true. Jump Game II: Track currentEnd (BFS level boundary) and nextReach. Increment jumps when hitting currentEnd. The reason: Jump Game I is binary (can/can't), Jump Game II is optimization (minimum jumps).
Key Insight
Q6: "At each node, I have choices" — how does this pattern apply to jump games? Jump Game I: "At index i, I choose to track maxReach. I don't choose WHICH jump to take — I just update the furthest I can go." Jump Game II: "At index i, I explore all jumps within current BFS level. When I've exhausted the level, I increment jumps." Jump Game III: "At index i, I MUST take EXACTLY arr[i] forward OR backward. Both choices must be explored (BFS/DFS)." Snakes & Ladders: "At cell i, I have exactly 6 dice roll choices (or fewer near the end). Each choice leads to a new cell (possibly teleported)."
📝 Key Takeaways
Jump Game I — Greedy maxReach: Track furthest reachable index. If i > maxReach at any point → impossible.
Jump Game II — BFS Levels: Track currentEnd (level boundary) and nextReach. Increment jumps when crossing the boundary.
Jump Game III — Graph BFS: Each index has exactly 2 outgoing edges (i+arr[i], i-arr[i]). BFS/DFS from start to find any zero-value node.
Snakes & Ladders — BFS on Board: Flatten Boustrophedon board, BFS from cell 1 to n². Each die roll = up to 6 edges with possible teleportation.
Mad City — Functional Graph: Each node has one outgoing edge. Graph = cycles + trees. 3-color DFS or topological removal to find safe nodes.
Game Routes — DP on DAG: Count paths in topological order. dp[v] = sum(dp[u]) for all edges u→v. Handles up to 10⁵ nodes with modulo.
Time Complexity: All solutions are O(n) or O(n + m) — linear in input size. This is optimal for graph problems.
Space Complexity: O(n) for BFS visited sets, O(n + m) for adjacency lists. Jump Games I and II are O(1) space!
The Graph Lens: Every reachability problem IS a graph problem. The skill is recognizing the graph structure (edges, weights, cycles) in the problem statement.
Practice! — The Playground below has 6 problems covering all patterns. Start with Jump Game I (greedy), then Snakes & Ladders (BFS on board), then Mad City (cycle detection), and finally Game Routes (DAG counting).
Note
🔮 What's Next? You've mastered jump and network games! Move to Tree Games & Strategiesto learn about game on leaves, tree tag, and permutation games on tree structures.
// At each index i, I have a CHOICE:// OPTION 1: Jump as far as I can (maximize reach)// OPTION 2: Stop here (but then I'm stuck if I can't reach the end)//// But wait — this is NOT about choosing ONE option.// It's about TRACKING the maximum reachable index as I go.//// Decision at each step:// "Can I REACH this index i?" (i <= maxReach)// If yes: "How far can I go from here?" (maxReach = max(maxReach, i + nums[i]))// If no: Game over — impossible to continue
function canJump(nums) { let maxReach = 0; const n = nums.length; for (let i = 0; i < n; i++) { if (i > maxReach) return false; // Can't reach this index maxReach = Math.max(maxReach, i + nums[i]); if (maxReach >= n - 1) return true; // Early exit } return true;}// Time: O(n), Space: O(1)// The GREEDY approach works because we only need REACHABILITY.// If any path can reach the end, maxReach will eventually cover it.
// Think of each JUMP as a BFS level:// Level 0: just index 0// Level 1: all indices reachable from index 0 in 1 jump// Level 2: all indices reachable from level 1 in 1 more jump// ...// Level k: reachable in k jumps//// We don't need an actual queue — we can simulate BFS// levels using two pointers:// currentEnd = last index of current BFS level// nextReach = furthest index reachable from current level
function jump(nums) { const n = nums.length; if (n === 1) return 0; let jumps = 0; let currentEnd = 0; // BFS level boundary let nextReach = 0; // Furthest reachable from current level for (let i = 0; i < n - 1; i++) { nextReach = Math.max(nextReach, i + nums[i]); if (i === currentEnd) { jumps++; // Finished exploring this BFS level currentEnd = nextReach; // Move to next level if (currentEnd >= n - 1) break; // Already reached the end } } return jumps;}// Time: O(n), Space: O(1)// This BFS-greedy hybrid is the optimal solution.// It's O(n) because each index is visited exactly once// in the loop, and we never backtrack.
// At each index i, EXACTLY two options:// Option A: Jump forward → i + arr[i]// Option B: Jump backward → i - arr[i]//// This creates a graph where each node has degree ≤ 2.// We need to find if ANY path leads to a node where arr[node] === 0.//// This is BFS/DFS on a graph — the "choose" part is which// direction to jump, but we must explore BOTH.
function canReach(arr, start) { const n = arr.length; const visited = new Array(n).fill(false); const queue = [start]; visited[start] = true; while (queue.length > 0) { const i = queue.shift(); if (arr[i] === 0) return true; // Found exit! // Two possible jumps from here for (const next of [i + arr[i], i - arr[i]]) { if (next >= 0 && next < n && !visited[next]) { visited[next] = true; queue.push(next); } } } return false; // Explored all reachable nodes, no exit found}// Time: O(n), Space: O(n) — each index visited at most once// The graph has n nodes and at most 2n edges (each node → 2 jumps)// BFS explores the connected component containing 'start'
// Row 0 (bottom): 1 2 3 4 5 6 7 8 9 10 (left→right)// Row 1 (above): 20 19 18 17 16 15 14 13 12 11 (right→left)// Row 2: 21 22 23 24 25 26 27 28 29 30 (left→right)// ...//// We need to convert (row, col) → cell number and vice versa.// Each cell i has up to 6 outgoing edges: i+1, i+2, ..., i+6// But if the destination has a snake/ladder (board value ≠ -1),// we teleport to that value instead.
function snakesAndLadders(board) { const n = board.length; // Convert (row, col) to cell number (1-indexed) const cellToPos = (cell) => { const r = Math.floor((cell - 1) / n); const row = n - 1 - r; // Board rows are reversed: 0=bottom const col = r % 2 === 0 // Even rows: left→right ? (cell - 1) % n : n - 1 - (cell - 1) % n; // Odd rows: right→left return [row, col]; }; const target = n * n; const queue = [1]; const dist = new Map(); dist.set(1, 0); while (queue.length > 0) { const curr = queue.shift(); const d = dist.get(curr); if (curr === target) return d; // Try all 6 die rolls for (let roll = 1; roll <= 6; roll++) { let next = curr + roll; if (next > target) continue; // Overshoot // Check for snake/ladder const [r, c] = cellToPos(next); if (board[r][c] !== -1) { next = board[r][c]; // Teleport! } if (!dist.has(next)) { dist.set(next, d + 1); queue.push(next); } } } return -1; // Impossible}// Time: O(n²), Space: O(n²)// BFS on n² nodes, each with ≤6 edges → O(6n²) = O(n²)
// Structure of any functional graph:// trees → cycle → ... → cycle// Each node eventually reaches a cycle//// Key insight:// - Nodes ON the cycle → UNSAFE (infinite loop)// - Nodes NOT on cycle → SAFE (path eventually ends)//// How to find cycle nodes?// 1. Topological removal: remove nodes with in-degree 0// 2. What remains = cycle nodes// 3. BFS/DFS from cycle nodes outward to mark unsafe nodes
// Approach 1: Topological Removal (Degree-Based)function findSafeCities(next) { const n = next.length; const inDegree = new Array(n).fill(0); // Count in-degrees for (let i = 0; i < n; i++) { inDegree[next[i]]++; } // Kahn's algorithm: remove nodes with in-degree 0 const queue = []; for (let i = 0; i < n; i++) { if (inDegree[i] === 0) queue.push(i); } const safe = new Array(n).fill(true); // Assume all safe while (queue.length > 0) { const u = queue.shift(); // u has in-degree 0 → not in a cycle → safe const v = next[u]; inDegree[v]--; if (inDegree[v] === 0) queue.push(v); } // Nodes still with in-degree > 0 are ON a cycle → unsafe for (let i = 0; i < n; i++) { safe[i] = inDegree[i] === 0; // Only safe if not in cycle } // Actually, nodes feeding into a cycle are also unsafe // (they eventually reach the cycle). The topological // removal above only removes nodes NOT leading to cycles. // // A node is safe ONLY if it leads to a dead end (out-degree 0 // after removing cycles). In a functional graph, safe nodes // are those whose path eventually reaches a node with no // incoming path from a cycle... This needs careful definition. // // Let's use DFS with 3-color marking instead: const WHITE = 0, GRAY = 1, BLACK = 2; const color = new Array(n).fill(WHITE); const result = []; function dfs(u) { if (color[u] === GRAY) return false; // Cycle detected! if (color[u] === BLACK) return true; // Already processed color[u] = GRAY; const safe = dfs(next[u]); color[u] = BLACK; if (safe) result.push(u); return safe; } for (let i = 0; i < n; i++) { if (color[i] === WHITE) dfs(i); } return result.sort((a, b) => a - b);}// Time: O(n), Space: O(n)// Each node visited once in DFS. 3-color marking detects// cycles naturally: GRAY = currently in stack (potential cycle).
// Define: dp[u] = number of paths from u to target (node n)//// Base case: dp[n] = 1 (one path from target to itself: stay put)// Transition: dp[u] = sum(dp[v]) for all edges u → v//// OR — process nodes in REVERSE topological order.// Since it's a DAG, topological order exists and gives us// a valid processing order where all successors are computed// before their predecessors (when going forward from source).
const MOD = 1000000007;function countPaths(n, edges) { // Build adjacency list const graph = Array.from({ length: n + 1 }, () => []); const inDegree = new Array(n + 1).fill(0); for (const [u, v] of edges) { graph[u].push(v); inDegree[v]++; } // Topological sort (Kahn's algorithm) const queue = []; for (let i = 1; i <= n; i++) { if (inDegree[i] === 0) queue.push(i); } const topo = []; while (queue.length > 0) { const u = queue.shift(); topo.push(u); for (const v of graph[u]) { inDegree[v]--; if (inDegree[v] === 0) queue.push(v); } } // DP in topological order const dp = new Array(n + 1).fill(0); dp[1] = 1; // Base: one path to start node for (const u of topo) { if (dp[u] === 0) continue; // Unreachable from start for (const v of graph[u]) { dp[v] = (dp[v] + dp[u]) % MOD; } } return dp[n]; // Number of paths from 1 to n}// Time: O(n + m), Space: O(n + m)// Topological sort + DP = linear in graph size// This is the standard "DP on DAG" pattern for counting paths.