288. Jump Game II

🔗 LeetCode Problem: 45. Jump Game II
📊 Difficulty: Medium
🏷️ Topics: Array, Dynamic Programming, Greedy, BFS

Problem Statement

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and
i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints: - 1 <= nums.length <= 10^4 - 0 <= nums[i] <= 1000 - It's guaranteed that you can reach nums[n - 1].

🌳 Visual Understanding - The Jump Problem

The Problem We're Solving:

Array: [2, 3, 1, 1, 4]
Index:  0  1  2  3  4

Start at index 0
Goal: Reach index 4 with MINIMUM jumps

At each position i:
  - nums[i] = maximum jump length
  - Can jump 1, 2, 3, ..., up to nums[i] steps forward

Question: What's the MINIMUM number of jumps needed? 🤔

Understanding "Minimum Jumps":

nums = [2, 3, 1, 1, 4]

At index 0 (value = 2):
  Can jump: 1 or 2 steps
  Reachable: index 1 or 2

At index 1 (value = 3):
  Can jump: 1, 2, or 3 steps
  Reachable: index 2, 3, or 4 ✓ (can reach end!)

At index 2 (value = 1):
  Can jump: 1 step
  Reachable: index 3

All Possible Paths:

nums = [2, 3, 1, 1, 4]

Path 1: 0 → 1 → 4
━━━━━━━━━━━━━━━━━━
  Jump 1: index 0 → 1 (1 step)
  Jump 2: index 1 → 4 (3 steps)
  Total: 2 jumps ✓ MINIMUM!

Path 2: 0 → 2 → 3 → 4
━━━━━━━━━━━━━━━━━━━━━━━━━
  Jump 1: index 0 → 2 (2 steps)
  Jump 2: index 2 → 3 (1 step)
  Jump 3: index 3 → 4 (1 step)
  Total: 3 jumps

Path 3: 0 → 1 → 2 → 3 → 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
  Jump 1: index 0 → 1 (1 step)
  Jump 2: index 1 → 2 (1 step)
  Jump 3: index 2 → 3 (1 step)
  Jump 4: index 3 → 4 (1 step)
  Total: 4 jumps

Multiple paths exist! We want MINIMUM = 2 ✓

Difference from Jump Game I:

Jump Game I (Problem 286):
  Question: "CAN we reach the end?"
  Answer: boolean (true/false)
  Focus: Feasibility

Jump Game II (Problem 288):
  Question: "MINIMUM jumps to reach end?"
  Answer: integer (count)
  Focus: Optimization

Same jumping mechanics, different objective!

🧠 The AHA Moment - Why Dynamic Programming?

Key Observation:

To find minimum jumps to last index:
  - We need to know minimum jumps to intermediate indices
  - If we know min jumps to index i, we can calculate for positions reachable from i

Recursive thinking:
  minJumps(lastIndex) = 1 + min(minJumps(j)) for all j that can reach lastIndex

This is an optimization problem! 🎯

Why Dynamic Programming?

1. OVERLAPPING SUBPROBLEMS:
   To find min jumps to index 5:
     - Check min jumps to 4, then jump from 4 to 5
     - Check min jumps to 3, then jump from 3 to 5
     - Check min jumps to 2, then jump from 2 to 5

   Position 3 might be checked from multiple sources!
   Cache results to avoid recomputation! ⚠️

2. OPTIMAL SUBSTRUCTURE:
   minJumps(n) = 1 + min(minJumps(i)) where i can reach n

   Optimal solution to larger problem built from optimal solutions to subproblems!

These properties = Perfect for DP! 🎯

🔴 Approach 1: Brute Force (Recursion)

📐 Function Definition

Function Signature:

int jump(int[] nums)
int minJumpsFrom(int position, int[] nums)

What it represents:

Input Parameter position: - Current index in the array - Where we are right now - Example: position=2 means "currently at index 2"

Input Parameter nums: - The jump array - nums[i] = max jump length at index i

Return Value (int): - Minimum number of jumps needed to reach last index FROM current position - Example: minJumpsFrom(0, nums) asks "min jumps from start to end?"

Purpose: - Find minimum jumps from given position to end - Try all possible jump lengths from current position - Recursive exploration of all paths, taking minimum

Key Understanding:

minJumpsFrom(2, [2,3,1,1,4]) asks:
  "Starting from index 2, what's minimum jumps to index 4?"

Process:
  - At index 2, nums[2] = 1
  - Can jump 1 step → check minJumpsFrom(3, nums)
  - If we jump to 3, total = 1 + minJumpsFrom(3, nums)
  - Return minimum across all possible jumps

💡 Intuition

From current position, try ALL possible jumps:
  - Jump 1 step, 2 steps, ..., up to nums[position] steps
  - For each jump, find min jumps from new position to end
  - Take MINIMUM across all options

Base case:
  - position == lastIndex: Already at end → return 0

Recursion explores all paths and finds minimum!

📝 Implementation

class Solution {
    public int jump(int[] nums) {
        return minJumpsFrom(0, nums);
    }

    private int minJumpsFrom(int position, int[] nums) {
        // Base case: reached the last index
        if (position >= nums.length - 1) {
            return 0;
        }

        int minJumps = Integer.MAX_VALUE;

        // Try all possible jumps from current position
        for (int jumpSize = 1; jumpSize <= nums[position]; jumpSize++) {
            int nextPosition = position + jumpSize;

            if (nextPosition < nums.length) {
                int jumpsFromNext = minJumpsFrom(nextPosition, nums);

                if (jumpsFromNext != Integer.MAX_VALUE) {
                    minJumps = Math.min(minJumps, 1 + jumpsFromNext);
                }
            }
        }

        return minJumps;
    }
}

🔍 Dry Run Example: nums = [2, 3, 1, 1, 4]

minJumpsFrom(0, [2,3,1,1,4])
├─ position=0, nums[0]=2, lastIndex=4
├─ Try jump 1: nextPosition=1
│  ├─ minJumpsFrom(1, nums)
│  │  ├─ position=1, nums[1]=3
│  │  ├─ Try jump 1: nextPosition=2
│  │  │  ├─ minJumpsFrom(2, nums)
│  │  │  │  ├─ position=2, nums[2]=1
│  │  │  │  ├─ Try jump 1: nextPosition=3
│  │  │  │  │  ├─ minJumpsFrom(3, nums)
│  │  │  │  │  │  ├─ position=3, nums[3]=1
│  │  │  │  │  │  ├─ Try jump 1: nextPosition=4
│  │  │  │  │  │  │  └─ minJumpsFrom(4, nums)
│  │  │  │  │  │  │     └─ position=4 == lastIndex → return 0
│  │  │  │  │  │  └─ return 1 + 0 = 1
│  │  │  │  └─ return 1 + 1 = 2
│  │  │  └─ minJumps = min(∞, 2) = 2
│  │  ├─ Try jump 2: nextPosition=3
│  │  │  └─ minJumpsFrom(3, nums) = 1 (cached above)
│  │  │  └─ minJumps = min(2, 1+1) = 2
│  │  ├─ Try jump 3: nextPosition=4
│  │  │  └─ minJumpsFrom(4, nums) = 0
│  │  │  └─ minJumps = min(2, 1+0) = 1
│  │  └─ return 1
│  └─ minJumps = min(∞, 1+1) = 2
├─ Try jump 2: nextPosition=2
│  └─ minJumpsFrom(2, nums) = 2 (calculated above)
│  └─ minJumps = min(2, 1+2) = 2
└─ return 2 ✓

Result: 2 jumps minimum!
Path: 0 → 1 → 4

📊 Complexity Analysis

Time Complexity: O(n^n) - Exponential!

At each position, try up to n jumps
Each jump leads to another position with up to n jumps
Tree height: up to n
Branching factor: up to n
Total: O(n^n) - VERY SLOW! 😰

Space Complexity: O(n)

Recursion stack depth: O(n) in worst case

Why This is Too Slow:

For nums = [1,1,1,1,1,1,1,1,1,1] (10 positions)
  From position 0: 1 possibility → position 1
  From position 1: 1 possibility → position 2
  ...
  But algorithm explores MANY redundant paths!

Many positions visited MULTIPLE times!
Need to cache results! 💡

🟡 Approach 2: Top-Down DP (Memoization)

📐 Function Definition

Function Signature:

int jump(int[] nums)
int minJumpsFrom(int position, int[] nums, int[] memo)

What it represents:

New Parameter memo: - Memoization array - memo[i] = minimum jumps from position i to end - -1 means "not yet calculated" - Caches results to avoid redundant calculations

Return Value: - Same as brute force: minimum jumps from position to end - But now with caching!

Purpose: - Same recursive logic as brute force - Add memoization to avoid recomputation - If we've already calculated minJumps from position i, reuse it!

💡 Intuition

Same as brute force, but with memory:
  Before calculating minJumpsFrom(i):
    - Check if memo[i] already has answer
    - If yes → return cached result
    - If no → calculate, store in memo[i], then return

Optimization:
  Each position calculated only ONCE
  Future calls reuse cached result
  Massive speedup! ⚡

📝 Implementation

class Solution {
    public int jump(int[] nums) {
        int[] memo = new int[nums.length];
        Arrays.fill(memo, -1);  // -1 means not calculated
        return minJumpsFrom(0, nums, memo);
    }

    private int minJumpsFrom(int position, int[] nums, int[] memo) {
        // Base case: at or past last index
        if (position >= nums.length - 1) {
            return 0;
        }

        // Check if already calculated
        if (memo[position] != -1) {
            return memo[position];  // Return cached result!
        }

        int minJumps = Integer.MAX_VALUE;

        // Try all possible jumps
        for (int jumpSize = 1; jumpSize <= nums[position]; jumpSize++) {
            int nextPosition = position + jumpSize;

            if (nextPosition < nums.length) {
                int jumpsFromNext = minJumpsFrom(nextPosition, nums, memo);

                if (jumpsFromNext != Integer.MAX_VALUE) {
                    minJumps = Math.min(minJumps, 1 + jumpsFromNext);
                }
            }
        }

        // Cache the result before returning
        memo[position] = minJumps;
        return minJumps;
    }
}

🔍 Detailed Dry Run: nums = [2, 3, 1, 1, 4]

Initial memo: [-1, -1, -1, -1, -1]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
minJumpsFrom(0)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Check memo[0]: -1 (not calculated)

Try jump 1 → minJumpsFrom(1)
  ┌──────────────────────────────────────────┐
  │ minJumpsFrom(1)                          │
  │ Check memo[1]: -1                        │
  │                                          │
  │ Try jump 1 → minJumpsFrom(2)             │
  │   ┌────────────────────────────────────┐ │
  │   │ minJumpsFrom(2)                    │ │
  │   │ Check memo[2]: -1                  │ │
  │   │                                    │ │
  │   │ Try jump 1 → minJumpsFrom(3)       │ │
  │   │   ┌──────────────────────────────┐ │ │
  │   │   │ minJumpsFrom(3)              │ │ │
  │   │   │ Check memo[3]: -1            │ │ │
  │   │   │                              │ │ │
  │   │   │ Try jump 1 → minJumpsFrom(4) │ │ │
  │   │   │   Base case: return 0        │ │ │
  │   │   │ minJumps = 1 + 0 = 1         │ │ │
  │   │   │ memo[3] = 1                  │ │ │
  │   │   └─ return 1                    │ │ │
  │   │                                    │ │
  │   │ minJumps = 1 + 1 = 2               │ │
  │   │ memo[2] = 2                        │ │
  │   └─ return 2                          │ │
  │                                          │
  │ minJumps = 1 + 2 = 3                     │
  │                                          │
  │ Try jump 2 → minJumpsFrom(3)             │
  │   Check memo[3]: 1 ✓ (CACHED!)          │
  │   minJumps = min(3, 1+1) = 2             │
  │                                          │
  │ Try jump 3 → minJumpsFrom(4)             │
  │   Base case: return 0                    │
  │   minJumps = min(2, 1+0) = 1             │
  │                                          │
  │ memo[1] = 1                              │
  └─ return 1                                │

minJumps = 1 + 1 = 2

Try jump 2 → minJumpsFrom(2)
  Check memo[2]: 2 ✓ (CACHED!)
  minJumps = min(2, 1+2) = 2

memo[0] = 2
return 2 ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Final memo: [2, 1, 2, 1, 0]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Meaning:
  memo[0] = 2: From index 0, need 2 jumps to reach end
  memo[1] = 1: From index 1, need 1 jump to reach end
  memo[2] = 2: From index 2, need 2 jumps to reach end
  memo[3] = 1: From index 3, need 1 jump to reach end
  memo[4] = 0: Already at end

Result: 2 jumps ✓

📊 Complexity Analysis

Time Complexity: O(n²)

Each position calculated once: O(n)
For each position, check up to n jumps: O(n)
Total: O(n) × O(n) = O(n²)

MUCH better than O(n^n)! ⚡

Space Complexity: O(n)

Memo array: O(n)
Recursion stack: O(n)
Total: O(n)

🟢 Approach 3: Bottom-Up DP

📐 Function Definition

DP Array:

int[] dp = new int[n]

What it represents:

dp[i]: - Minimum number of jumps needed to reach last index FROM position i - dp[lastIndex] = 0 (base case: already at end) - We build answers from right to left!

Purpose: - Eliminate recursion - Build table iteratively - Start from end, work backwards to start

💡 Intuition

Instead of recursion (top-down):
  Build answers bottom-up!

Start from the end:
  dp[lastIndex] = 0 (at end, need 0 jumps)

For each position i (from right to left):
  Try all possible jumps from i
  Find minimum jumps among all reachable positions
  dp[i] = 1 + min(dp[reachable positions])

Answer: dp[0]

📝 Implementation

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);

        // Base case: already at last index
        dp[n - 1] = 0;

        // Build from right to left
        for (int i = n - 2; i >= 0; i--) {
            // Try all possible jumps from position i
            for (int jumpSize = 1; jumpSize <= nums[i]; jumpSize++) {
                int nextPos = i + jumpSize;

                if (nextPos < n && dp[nextPos] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], 1 + dp[nextPos]);
                }
            }
        }

        return dp[0];
    }
}

🔍 Detailed Dry Run: nums = [2, 3, 1, 1, 4]

Input: nums = [2, 3, 1, 1, 4]
n = 5, lastIndex = 4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

dp = [∞, ∞, ∞, ∞, 0]
     [0, 1, 2, 3, 4] ← indices

dp[4] = 0 (base case: at end)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION - Building backwards
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Iteration 1: i = 3
━━━━━━━━━━━━━━━━
Position 3, nums[3] = 1
Can jump 1 step

Try jump 1: nextPos = 4
  dp[4] = 0
  dp[3] = min(∞, 1 + 0) = 1

dp = [∞, ∞, ∞, 1, 0]

Meaning: From index 3, need 1 jump to reach end


Iteration 2: i = 2
━━━━━━━━━━━━━━━━
Position 2, nums[2] = 1
Can jump 1 step

Try jump 1: nextPos = 3
  dp[3] = 1
  dp[2] = min(∞, 1 + 1) = 2

dp = [∞, ∞, 2, 1, 0]

Meaning: From index 2, need 2 jumps to reach end


Iteration 3: i = 1
━━━━━━━━━━━━━━━━
Position 1, nums[1] = 3
Can jump 1, 2, or 3 steps

Try jump 1: nextPos = 2
  dp[2] = 2
  dp[1] = min(∞, 1 + 2) = 3

Try jump 2: nextPos = 3
  dp[3] = 1
  dp[1] = min(3, 1 + 1) = 2

Try jump 3: nextPos = 4
  dp[4] = 0
  dp[1] = min(2, 1 + 0) = 1 ✓ BEST!

dp = [∞, 1, 2, 1, 0]

Meaning: From index 1, need 1 jump to reach end (jump directly to 4)


Iteration 4: i = 0 (FINAL)
━━━━━━━━━━━━━━━━━━━━━━━━━
Position 0, nums[0] = 2
Can jump 1 or 2 steps

Try jump 1: nextPos = 1
  dp[1] = 1
  dp[0] = min(∞, 1 + 1) = 2

Try jump 2: nextPos = 2
  dp[2] = 2
  dp[0] = min(2, 1 + 2) = 2

dp = [2, 1, 2, 1, 0]
      ↑
   ANSWER!

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPLETE DP TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Index:   0     1     2     3     4
        ┌────┬────┬────┬────┬────┐
dp[]    │ 2  │ 1  │ 2  │ 1  │ 0  │
        └────┴────┴────┴────┴────┘
         ↑                    ↑
      Answer              Base case

Meaning:
  dp[0] = 2: From start, need 2 jumps to reach end ✓
  dp[1] = 1: From index 1, need 1 jump
  dp[2] = 2: From index 2, need 2 jumps
  dp[3] = 1: From index 3, need 1 jump
  dp[4] = 0: Already at end

Path reconstruction:
  From 0: Can reach 1 or 2
    dp[1] = 1, dp[2] = 2 → Choose 1 (minimum)
  From 1: Can reach 2, 3, or 4
    dp[2] = 2, dp[3] = 1, dp[4] = 0 → Choose 4 (minimum)

  Optimal path: 0 → 1 → 4 (2 jumps) ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 2 jumps minimum ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

📊 Complexity Analysis

Time Complexity: O(n²)

Loop from n-2 to 0: O(n)
For each position, try up to n jumps: O(n)
Total: O(n) × O(n) = O(n²)

Same as top-down, but no recursion overhead!

Space Complexity: O(n)

DP array: O(n)
No recursion stack: O(1)
Total: O(n)

🔵 Approach 4: BFS (Level-by-Level) - The Most Intuitive!

🎨 Building Intuition - Why BFS is Natural

Let's forget about code for a moment and think like a human:

Imagine you're standing at position 0.
Your friends are standing at ALL other positions.

You want to reach your friend at the LAST position.
But there are rules:
  - You can only move forward
  - From each position, you can jump to nearby friends
  - You want MINIMUM jumps

How would YOU solve this naturally?

The Natural Human Approach:

Step 1: "From where I am (position 0), who can I reach in 1 jump?"
  Look at all friends you can reach in 1 jump
  Mark them with number "1"

Step 2: "From those friends, who can THEY reach in 1 more jump?"
  Look at all NEW friends reachable
  Mark them with number "2"

Step 3: "Continue until you reach the last friend"
  The number on the last friend = minimum jumps!

THIS IS BFS! This is how humans naturally think!

📚 Real-World Analogy: The Party Invitation

You're at a party and want to deliver a message to someone at the far end.

Rules:
  - You can only whisper to people near you
  - They can whisper to people near them
  - You want the message to reach the target in MINIMUM steps

How does the message spread?

Round 1: You whisper to friends in your group
  [You] → whispers to → [Friend A, Friend B]
  Message reaches: Friend A and B (1 whisper)

Round 2: Friend A and B whisper to their neighbors
  [Friend A] → whispers to → [Friend C, Friend D]
  [Friend B] → whispers to → [Friend E]
  Message reaches: C, D, E (2 whispers)

Round 3: They whisper to their neighbors
  And so on...

When does target get the message?
  At round N = N whispers = MINIMUM whispers!

THIS IS EXACTLY BFS! 
Rounds = Levels = Jumps!

🎯 Connecting to Jump Game

Position 0 = You
Other positions = Your friends
Jump = Whisper/reach

nums = [2, 3, 1, 1, 4]

You at position 0:
  "I can reach friends at position 1 and 2"

Friends at positions 1 and 2:
  Friend 1: "I can reach positions 2, 3, 4"
  Friend 2: "I can reach position 3"

Notice:
  - Round 0: Position [0]
  - Round 1: Positions [1, 2]  ← Reachable in 1 jump
  - Round 2: Positions [3, 4]  ← Reachable in 2 jumps

Position 4 first appears in Round 2!
Answer: 2 jumps! ✓

BFS explores round by round = level by level = jump by jump!

🌊 The Wave Analogy - Most Intuitive!

Think of jumping like ripples in a pond:

Drop a stone at position 0:
  ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  Ripple 0: Just the stone
    [●]░░░░
     0 1 2 3 4

  Ripple 1: First wave spreads out
    [●●●]░░
     0 1 2 3 4
    Reached: positions 1, 2
    Ripples so far: 1

  Ripple 2: Wave spreads further
    [●●●●●]
     0 1 2 3 4
    Reached: positions 3, 4 (including the end!)
    Ripples so far: 2

  How many ripples to reach position 4? → 2! ✓

Each ripple = 1 jump
Count ripples = count jumps!

THIS IS WHY BFS WORKS!

📝 BFS Implementation - With Human Thinking

class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1) return 0;  // Already at destination

        // The "party guest list" for each round
        Queue<Integer> currentRound = new LinkedList<>();

        // Keep track of who we've already reached
        boolean[] reached = new boolean[nums.length];

        // Start: we're at position 0
        currentRound.offer(0);
        reached[0] = true;

        int rounds = 0;  // Number of rounds of spreading

        while (!currentRound.isEmpty()) {
            // How many people in this round?
            int peopleInThisRound = currentRound.size();
            rounds++;  // Starting a new round

            // For each person in this round
            for (int i = 0; i < peopleInThisRound; i++) {
                int currentPosition = currentRound.poll();

                // "From my position, who can I reach?"
                // I can jump 1, 2, ..., up to nums[currentPosition] steps

                for (int jumpSize = 1; jumpSize <= nums[currentPosition]; jumpSize++) {
                    int newPosition = currentPosition + jumpSize;

                    // Did we reach the end?
                    if (newPosition >= nums.length - 1) {
                        return rounds;  // Found it! This many rounds!
                    }

                    // If we haven't reached this person yet
                    if (!reached[newPosition]) {
                        reached[newPosition] = true;
                        currentRound.offer(newPosition);  // Add to next round
                    }
                }
            }
        }

        return rounds;
    }
}

🔍 Complete Visual Walkthrough - Like Telling a Story

nums = [2, 3, 1, 1, 4]

THE STORY:

You're at position 0. Your goal: reach position 4.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ROUND 0 (Setup)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

You: "I'm at position 0!"

Current round: [0]
Reached: {0}
Rounds completed: 0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ROUND 1 - "Who can I reach in 1 jump?"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

rounds = 1

Processing position 0:
  You: "I'm at 0, nums[0]=2, so I can jump 1 or 2 steps"

  Jump 1 step → position 1
    You: "Can I reach position 1? Yes!"
    Position 1: "I haven't been reached yet!"
    Add position 1 to next round

  Jump 2 steps → position 2
    You: "Can I reach position 2? Yes!"
    Position 2: "I haven't been reached yet!"
    Add position 2 to next round

Next round: [1, 2]
Reached: {0, 1, 2}
Rounds completed: 1

Visual:
  [●●●]░░  ← After round 1, reached up to position 2
   0 1 2 3 4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ROUND 2 - "Who can positions 1 and 2 reach?"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

rounds = 2

Processing position 1:
  Position 1: "I'm at 1, nums[1]=3, I can jump 1, 2, or 3 steps"

  Jump 1 step → position 2
    Position 2: "I'm already reached! Skip me."

  Jump 2 steps → position 3
    Position 3: "I haven't been reached yet!"
    Add position 3 to next round

  Jump 3 steps → position 4
    Position 4: "That's the END! You found me!"

    🎉 FOUND THE END! 🎉

    Return rounds = 2

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 2 jumps
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

The story:
  Round 0: You're at position 0
  Round 1: You reach positions 1 and 2
  Round 2: From position 1, you reach the END (position 4)!

  Total rounds = 2 = Minimum jumps! ✓

Visual of rounds:
  Round 0: [●]░░░░
           0 1 2 3 4

  Round 1: [●●●]░░
           0 1 2 3 4

  Round 2: [●●●●●]  ← Reached the end!
           0 1 2 3 4

💡 Why BFS is Perfect for This Problem

BFS has a GUARANTEE:
  "The first time you reach a position = minimum distance to that position"

Why?
  Because BFS explores positions in ORDER of distance:
    - Distance 0 positions first (just start)
    - Then distance 1 positions (reachable in 1 jump)
    - Then distance 2 positions (reachable in 2 jumps)
    - And so on...

When we first reach the end:
  That's the MINIMUM number of jumps! Guaranteed! ✓

This is why BFS is PERFECT for "minimum steps" problems!

📊 Complexity Analysis

Time: O(n²)

Each position visited once: O(n)
For each position, check up to n jumps: O(n)
Total: O(n²)

Space: O(n)

Queue + reached array: O(n)

🟣 Approach 5: Greedy (Optimal Solution)

🎨 Understanding Greedy - Simple and Clear

Forget fancy terms. Let's understand this like a normal person would.

The Simple Question

You learned BFS: It finds minimum jumps by exploring level by level

BFS does this:
  Level 0: [0]
  Level 1: [1, 2]
  Level 2: [3, 4] ← Found end! Answer: 2 levels = 2 jumps

Question: "Do we NEED a queue to do this?"

Let's think...

The Key Observation

Look at BFS levels again:

nums = [2, 3, 1, 1, 4]

Level 0: Just position 0
Level 1: Positions 1, 2
Level 2: Positions 3, 4

Notice something?
  Each level is a CONTINUOUS RANGE!

  Level 1 = "everything from 0 to 2"
  Level 2 = "everything from 0 to 4"

So instead of tracking individual positions in a queue:
  Just track: "How far does this level extend?"

Level 0: extends to position 0
Level 1: extends to position 2
Level 2: extends to position 4

Just track the ENDPOINT of each level!
No queue needed! This is Greedy! 🎯

Building Understanding Step by Step

Step 1: Understanding "How far can I reach?"

nums = [2, 3, 1, 1, 4]

Starting at position 0:
  From position 0, I can jump to: 1 or 2

  Question: "With 1 jump, what's the FURTHEST I can reach?"
  Answer: Position 2

This is simple! Just: position + nums[position]
  0 + 2 = 2

So: "With 1 jump from start, I can reach UP TO position 2"

Step 2: What about the NEXT jump?

Now I know: "With 1 jump, I can be anywhere in positions [0, 1, 2]"

Question: "With 2 jumps total, how far can I reach?"

I need to check: "From ANY position in [0,1,2], what's the furthest?"

From position 0: can reach 0+2=2
From position 1: can reach 1+3=4  ← This is furthest!
From position 2: can reach 2+1=3

Furthest overall: 4

So: "With 2 jumps, I can reach UP TO position 4"

Position 4 is the end! Answer: 2 jumps! ✓

The Pattern

Do you see the pattern?

Jump 1: Check positions [0], find furthest reach = 2
Jump 2: Check positions [0,1,2], find furthest reach = 4 (the end!)

General pattern:
  For each jump, we explore a RANGE of positions
  Find the furthest position reachable from that range
  That becomes the range for the next jump

We count: "How many such ranges until we reach the end?"
That's the minimum jumps!

The Two Simple Numbers We Track

Number 1: Where does current range end?

Let's call this: currentRangeEnd

Starting: currentRangeEnd = 0 (just position 0)

After exploring [0], we found we can reach up to 2:
  currentRangeEnd = 2

After exploring [0,1,2], we found we can reach up to 4:
  currentRangeEnd = 4

Simple! It's just: "How far does my current range extend?"

Number 2: What's the furthest I've seen so far?

Let's call this: maxReach

As I walk through positions, I keep updating:
  "What's the furthest position I could reach?"

At position 0: maxReach = 0+2 = 2
At position 1: maxReach = max(2, 1+3) = 4
At position 2: maxReach = max(4, 2+1) = 4

This tracks the furthest position possible from current range.

Putting It Together

The algorithm is simple:

1. Walk through positions one by one (i = 0, 1, 2, ...)

2. At each position i:
   Update maxReach = max(maxReach, i + nums[i])
   (Keep track of furthest we've seen)

3. When we reach the end of current range (i == currentRangeEnd):
   - We've finished exploring this range!
   - Count a jump
   - The next range extends to maxReach
   - Set currentRangeEnd = maxReach

4. Stop when currentRangeEnd reaches the end

That's it! No complicated metaphors needed!

Visual Walkthrough

nums = [2, 3, 1, 1, 4]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
SETUP
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

jumps = 0
currentRangeEnd = 0
maxReach = 0

Meaning:
  - Haven't jumped yet
  - Current range is just [0]
  - Haven't explored anything yet

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
POSITION i=0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Value at position 0: nums[0] = 2

Update maxReach:
  From position 0, can reach: 0 + 2 = 2
  maxReach = max(0, 2) = 2

Check: Is i (0) == currentRangeEnd (0)?
  YES! We've reached the end of current range [0]

Action:
  - We explored range [0]
  - Found furthest reach is 2
  - Make a jump!

  jumps = 1
  currentRangeEnd = 2

Status:
  jumps = 1
  currentRangeEnd = 2 (next range is [0,1,2])
  maxReach = 2

Meaning: "With 1 jump, I can reach up to position 2"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
POSITION i=1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Value at position 1: nums[1] = 3

Update maxReach:
  From position 1, can reach: 1 + 3 = 4
  maxReach = max(2, 4) = 4

Check: Is i (1) == currentRangeEnd (2)?
  NO! Still exploring current range [0,1,2]

Status:
  jumps = 1
  currentRangeEnd = 2
  maxReach = 4 (updated!)

Meaning: "Still in range [0,1,2], but found we can reach 4 from here"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
POSITION i=2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Value at position 2: nums[2] = 1

Update maxReach:
  From position 2, can reach: 2 + 1 = 3
  maxReach = max(4, 3) = 4 (no change)

Check: Is i (2) == currentRangeEnd (2)?
  YES! We've reached the end of current range [0,1,2]

Action:
  - We explored entire range [0,1,2]
  - Found furthest reach is 4
  - Make a jump!

  jumps = 2
  currentRangeEnd = 4

Status:
  jumps = 2
  currentRangeEnd = 4 (next range extends to 4)
  maxReach = 4

Meaning: "With 2 jumps, we can reach position 4 (the end!)"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
DONE!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

currentRangeEnd (4) = last position (4)
We can reach the end!

Answer: 2 jumps ✓

SUMMARY:
  Jump 1: Explored [0], found can reach up to 2
  Jump 2: Explored [0,1,2], found can reach up to 4 ✓

  Total: 2 jumps!

The Code - Now You Understand It

class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1) return 0;

        int jumps = 0;
        int currentRangeEnd = 0;    // How far does current range extend?
        int maxReach = 0;            // Furthest we've seen so far

        for (int i = 0; i < nums.length - 1; i++) {

            // Update furthest reachable
            maxReach = Math.max(maxReach, i + nums[i]);

            // Reached end of current range?
            if (i == currentRangeEnd) {
                jumps++;                      // Count this jump
                currentRangeEnd = maxReach;   // Next range extends to maxReach
            }
        }

        return jumps;
    }
}

Understanding each line:

Line: maxReach = Math.max(maxReach, i + nums[i]);
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"From position i, I can reach i + nums[i]"
"Keep track of the furthest position I've seen"

Line: if (i == currentRangeEnd)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"Have I finished exploring current range?"
"If yes, time to move to next range"

Line: jumps++;
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"Making a jump to the next range"

Line: currentRangeEnd = maxReach;
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"Next range extends to the furthest position I found"

Why This Works - Simple Proof

Question: "Why is this the minimum?"

Answer: Because we explore COMPLETELY before jumping!

Look at the algorithm:
  1. We explore ENTIRE current range [0 to currentRangeEnd]
  2. We find the ABSOLUTE FURTHEST position from any position in that range
  3. THEN we make a jump to that furthest position

Since we pick the absolute furthest each time:
  We minimize the number of jumps needed!

Example:
  Range [0,1,2]: We check ALL three positions
  We find the furthest any of them can reach (position 4)
  This is the BEST choice for minimizing jumps!

We can't do better because we've checked ALL possibilities! ✓

Comparison: BFS vs Greedy

Let's compare them side by side:

nums = [2, 3, 1, 1, 4]

BFS APPROACH:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Uses queue: [0]
Process 0 → Add [1, 2] to queue
Level 1 complete → jumps = 1

Uses queue: [1, 2]  
Process 1 → Add [3, 4] to queue
Process 2 → Add [3] to queue (already have it)
Level 2 complete → jumps = 2
Found end!

Needs queue (space: O(n))

GREEDY APPROACH:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
currentRangeEnd = 0
Explore up to position 0 → maxReach = 2
Range complete → jumps = 1, currentRangeEnd = 2

currentRangeEnd = 2
Explore up to position 2 → maxReach = 4
Range complete → jumps = 2, currentRangeEnd = 4
Found end!

No queue (space: O(1))

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BOTH GET SAME ANSWER: 2 jumps!

But Greedy:
  ✓ No queue needed
  ✓ Simpler logic  
  ✓ Faster (O(n) vs O(n²))
  ✓ Less space (O(1) vs O(n))

The Key Insight

BFS and Greedy solve the SAME problem:
  "Count how many levels/ranges needed to reach the end"

BFS: Uses queue to manage levels explicitly
GREEDY: Tracks range boundaries with two numbers

It's the same idea, different implementation!

Greedy is just an optimization of BFS! 🎯

Complete Example Walkthrough

nums = [1, 2, 1, 1, 1]

Let me walk through this completely:

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIAL STATE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

jumps = 0
currentRangeEnd = 0
maxReach = 0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0: nums[0]=1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

maxReach = max(0, 0+1) = 1
i == currentRangeEnd? (0 == 0) YES!
  jumps = 1
  currentRangeEnd = 1

State: jumps=1, currentRangeEnd=1, maxReach=1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=1: nums[1]=2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

maxReach = max(1, 1+2) = 3
i == currentRangeEnd? (1 == 1) YES!
  jumps = 2
  currentRangeEnd = 3

State: jumps=2, currentRangeEnd=3, maxReach=3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=2: nums[2]=1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

maxReach = max(3, 2+1) = 3
i == currentRangeEnd? (2 == 3) NO

State: jumps=2, currentRangeEnd=3, maxReach=3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=3: nums[3]=1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

maxReach = max(3, 3+1) = 4
i == currentRangeEnd? (3 == 3) YES!
  jumps = 3
  currentRangeEnd = 4

State: jumps=3, currentRangeEnd=4, maxReach=4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
DONE! (currentRangeEnd = 4 = last index)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Answer: 3 jumps

Ranges:
  Jump 1: [0] → can reach up to 1
  Jump 2: [0,1] → can reach up to 3  
  Jump 3: [0,1,2,3] → can reach up to 4 ✓

Practice Problem

Try it yourself: nums = [2, 1, 3, 1, 1, 1]

Trace through step by step:

i=0: maxReach=?, currentRangeEnd=?, jumps=?
i=1: maxReach=?, currentRangeEnd=?, jumps=?
i=2: maxReach=?, currentRangeEnd=?, jumps=?
...

What's the answer?

(Try it, then check: Answer is 2 jumps)

Complexity Analysis

Time: O(n)

Single pass through array: O(n)
Each position processed once: O(1) per position
Total: O(n) ✓

OPTIMAL! Can't do better!

Space: O(1)

Only 3 variables: jumps, currentRangeEnd, maxReach
Constant space! ✓

Summary - The Simple Truth

Greedy approach is just:
  1. Track ranges, not individual positions
  2. Explore each range completely
  3. Find furthest reach from that range
  4. Count how many ranges needed

No fancy metaphors needed!
Just simple, logical thinking! ✓

Remember:
  currentRangeEnd = "How far does current range go?"
  maxReach = "Furthest I've seen while exploring"
  jumps = "How many ranges I've completed"

That's it! 🎯

📊 Approach Comparison

┌──────────────────┬─────────────┬──────────┬──────────────────┐
│ Approach         │ Time        │ Space    │ Key Insight      │
├──────────────────┼─────────────┼──────────┼──────────────────┤
│ Brute Force      │ O(n^n)      │ O(n)     │ Try all paths    │
│ Top-Down DP      │ O(n²)       │ O(n)     │ Cache results    │
│ Bottom-Up DP     │ O(n²)       │ O(n)     │ Build table      │
│ BFS              │ O(n²)       │ O(n)     │ Level-by-level   │
│ Greedy Ranges    │ O(n)        │ O(1)     │ Range extensions │
└──────────────────┴─────────────┴──────────┴──────────────────┘

Greedy Ranges is clearly optimal! ✨

💡 Key Learnings

1. PROBLEM EVOLUTION:
   ✓ Brute force explores all paths → Too slow
   ✓ DP optimizes with memoization → Better
   ✓ BFS thinks in levels → Natural
   ✓ Greedy uses range concept → Optimal!

2. RANGE-BASED THINKING:
   ✓ One jump opens a RANGE, not single position
   ✓ Track current range (currentEnd)
   ✓ Track next range (furthest)
   ✓ Count range extensions = count jumps

3. GREEDY CORRECTNESS:
   ✓ Explore entire current range
   ✓ Find furthest reachable
   ✓ Extend to that furthest position
   ✓ This guarantees minimum jumps

4. WHEN TO JUMP:
   ✓ Key insight: jump when i == currentEnd
   ✓ This is boundary of current range
   ✓ Must jump to extend range further

5. OPTIMIZATION JOURNEY:
   ✓ O(n^n) → O(n²) → O(n)
   ✓ Each step: better understanding
   ✓ Final greedy solution: elegant!

⚠️ Common Mistakes

// Mistake 1: Forgetting edge case
public int jump(int[] nums) {
    // ❌ Forgot to check if already at end
    int jumps = 0;
    // ...
}

// ✓ CORRECT
if (nums.length == 1) return 0;

// Mistake 2: Wrong loop condition
for (int i = 0; i < nums.length; i++) {  // ❌ Should stop at n-1
}

// ✓ CORRECT
for (int i = 0; i < nums.length - 1; i++) {
}

// Mistake 3: Not updating furthest
if (i == currentEnd) {
    jumps++;
    currentEnd = i + nums[i];  // ❌ Should use furthest!
}

// ✓ CORRECT
furthest = Math.max(furthest, i + nums[i]);  // Track maximum
if (i == currentEnd) {
    jumps++;
    currentEnd = furthest;  // Use the maximum
}

// Mistake 4: Jumping at wrong time
furthest = Math.max(furthest, i + nums[i]);
if (furthest >= nums.length - 1) {  // ❌ Wrong trigger
    jumps++;
}

// ✓ CORRECT - Jump when reaching current range boundary
if (i == currentEnd) {
    jumps++;
    currentEnd = furthest;
}

🎉 Congratulations!

You've mastered Jump Game II - from brute force to optimal greedy!

What You Learned:

✅ Minimum Path Problems - Finding optimal number of steps
✅ Brute Force Recursion - Trying all paths
✅ Top-Down DP - Memoization to cache results
✅ Bottom-Up DP - Building table iteratively
✅ BFS Approach - Level-by-level exploration
✅ Greedy Optimization - Range-based thinking
✅ O(n^n) to O(n) - Complete optimization journey

The Beautiful Journey:

Brute Force (O(n^n)):
  "Try every possible jump sequence"
  → Exponential! Way too slow! 😰

Top-Down DP (O(n²)):
  "Cache which positions need how many jumps"
  → Much better! Polynomial time! 😊

Bottom-Up DP (O(n²)):
  "Build jump count table backwards"
  → Clear! No recursion! 😊

BFS (O(n²)):
  "Explore level by level"
  → Natural for minimum steps! 😊

Greedy (O(n)):
  "Think in ranges, count extensions!"
  → Optimal! Linear time, constant space! 🚀⭐

Pattern Evolution:

Problem 286 (Jump Game I): Can reach? → Greedy O(n)
Problem 288 (Jump Game II): Min jumps? → Greedy O(n)

Same problem family, same greedy pattern!
But Jump Game II needs TWO boundaries (currentEnd, furthest)
while Jump Game I needs ONE (furthest)

Understanding this evolution = mastery! 🎯

You've now mastered the complete progression from brute force through DP to optimal greedy! 🚀✨

🎯 Pattern Recognition - Minimum Steps Problems

Core Pattern: BFS/Greedy Range Extension

Template for minimum steps/jumps problems:

Think in LEVELS or RANGES:
  currentEnd = boundary of current level/range
  furthest = boundary of next level/range
  steps = 0

  For each position i:
    Update furthest with reachable positions
    If i == currentEnd:
      steps++
      currentEnd = furthest

Key insight: Count level/range changes!

🎓 Practice Exercise - Trace It Yourself!

Try this: nums = [1, 2, 3, 1, 1, 1]

Use the GREEDY approach:

Initial:
  jumps = 0, currentEnd = 0, furthest = 0

Trace each position:

i=0: 
  furthest = max(0, 0+1) = ___
  i == currentEnd? ___
  If yes: jumps = ___, currentEnd = ___

i=1:
  furthest = max(___, 1+2) = ___
  i == currentEnd? ___
  If yes: jumps = ___, currentEnd = ___

i=2:
  furthest = max(___, 2+3) = ___
  i == currentEnd? ___
  If yes: jumps = ___, currentEnd = ___

Continue until i = 4 (don't process last position!)

What is the minimum number of jumps?

Solution below (don't peek!)

✅ Solution to Practice Exercise

nums = [1, 2, 3, 1, 1, 1]
Length = 6, lastIndex = 5

i=0: 
  furthest = max(0, 0+1) = 1
  i == currentEnd (0 == 0)? YES
  jumps = 1, currentEnd = 1

i=1:
  furthest = max(1, 1+2) = 3
  i == currentEnd (1 == 1)? YES
  jumps = 2, currentEnd = 3

i=2:
  furthest = max(3, 2+3) = 5
  i == currentEnd (2 == 3)? NO

i=3:
  furthest = max(5, 3+1) = 5
  i == currentEnd (3 == 3)? YES
  jumps = 3, currentEnd = 5 (reached end!)

i=4:
  furthest = max(5, 4+1) = 5
  i == currentEnd (4 == 5)? NO

Result: 3 jumps

Ranges:
  Jump 0: [0]
  Jump 1: [0, 1]
  Jump 2: [0, 1, 2, 3]
  Jump 3: [0, 1, 2, 3, 4, 5] ✓

Minimum jumps: 3 ✓

⚠️ Important Edge Cases to Test

// Single element
nums = [0]           // Expected: 0 (already at end)

// Two elements
nums = [1, 1]        // Expected: 1
nums = [2, 1]        // Expected: 1

// Already can reach end in one jump
nums = [5, 1, 1, 1, 1]  // Expected: 1

// Need multiple jumps
nums = [1, 1, 1, 1]  // Expected: 3
nums = [2, 3, 1, 1, 4]  // Expected: 2

// Large jump values
nums = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 0]  // Expected: 2

// All same values
nums = [1, 1, 1, 1, 1]  // Expected: 4 (must hop through each)

📝 Quick Revision Notes

🎯 Core Concept

Problem: Given array where nums[i] = max jump length at position i, find minimum jumps to reach last index from index 0.

Five Approaches: 1. Brute Force: Try all paths → O(n^n) time ❌ 2. Top-Down DP: Memoization → O(n²) time, O(n) space ✓ 3. Bottom-Up DP: Iterative table → O(n²) time, O(n) space ✓ 4. BFS: Level-by-level → O(n²) time, O(n) space ✓ 5. Greedy: Range extension → O(n) time, O(1) space ⭐⭐⭐

Key Insight: Think in RANGES, not positions! Count how many range extensions (jumps) needed to reach end.

⚡ Quick Implementation - Greedy (Optimal)

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
  public int jump(int[] a) {
    // return recursive(0, a);

    // Integer[] memo = new Integer[a.length + 1];
    // return topDown(0, a, memo);

    // return bottomUp(a);

    // return bfs(a);

    return greedy(a);
  }

  private int bfs(int[] a) {
    if (a.length == 1) {
      return 0;
    }

    // Example: [2, 3, 1, 1, 4]
    // It is similar to graph problem
    // From current index, what are all indices we can reach.
    // Level 1 (jump 0)
    // 0 -> 1, 2 => push these to queue
    // Level 2 (jump 1)
    // 1 -> 2, 3, 4 (indices I can reach) => push these to queue
    // 2 -> 3 => maintain visited to avoid duplicates
    int jumps = 0;

    HashSet<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    // step 1: start journey at i = 0
    queue.offer(0);

    while (!queue.isEmpty()) {
      int size = queue.size();
      jumps++;

      // step 2: consider elements at some particular level
      for (int i = 0; i < size; i++) {
        int polled = queue.poll();

        // step 3: from the current polled
        // element, which elements I can reach
        for (int step = 1; step <= a[polled]; step++) {
          int nextStep = step + polled;

          // step 4: check first if we have reached destination
          if (nextStep >= a.length - 1) {
            return jumps;
          }

          // step 5: else add to next level for further exploration
          if (!visited.contains(nextStep)) {
            queue.offer(nextStep);
            visited.add(nextStep);
          }
        }
      }
    }

    return jumps;
  }

  private int greedy(int[] a) {
    int n = a.length;
    if (n == 1) {
      return 0;
    }

    int maxCanReach = 0;
    int jumps = 0;
    int currReachEnd = 0;

    // step 1: start journey at every index
    for (int i = 0; i < n - 1; i++) {
      // step 2: how much farthest i can reach from the current index
      maxCanReach = Math.max(maxCanReach, i + a[i]);

      // step 3: till I reach above max, I do not need to explore next
      if (i == currReachEnd) {
        jumps++;
        currReachEnd = maxCanReach;
      }
    }

    // step 4: all elements done
    return jumps;
  }

  private int bottomUp(int[] a) {
    int n = a.length;
    Integer[] dp = new Integer[n];

    // same base case - already at the last step
    dp[a.length - 1] = 0;

    for (int index = n - 2; index >= 0; index--) {
      dp[index] = Integer.MAX_VALUE;

      for (int step = 1; step <= a[index]; step++) {
        if (index + step <= n && dp[index + step] != Integer.MAX_VALUE) {
          dp[index] = Math.min(dp[index], 1 + dp[index + step]);
        }

      }
    }

    return dp[0];
  }

  private int topDown(int index, int[] a, Integer[] memo) {
    // base case
    if (index >= a.length - 1) {
      return 0;
    }

    if (memo[index] != null) {
      return memo[index];
    }

    int minSteps = Integer.MAX_VALUE;

    for (int step = 1; step <= a[index]; step++) {
      int curr = topDown(index + step, a, memo);

      if (curr != Integer.MAX_VALUE) {
        minSteps = Math.min(minSteps, 1 + curr);
      }
    }

    return memo[index] = minSteps;
  }

  private int recursive(int index, int[] a) {
    // base case
    if (index >= a.length - 1) {
      return 0;
    }

    int minSteps = Integer.MAX_VALUE;

    for (int step = 1; step <= a[index]; step++) {
      int curr = recursive(index + step, a);

      if (curr != Integer.MAX_VALUE) {
        minSteps = Math.min(minSteps, 1 + curr);
      }
    }

    // Above never happened, so return MAX
    return minSteps;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.jump(new int[] { 2, 3, 1, 1, 4 }) == 2);
    System.out.println(s.jump(new int[] { 2, 3, 0, 1, 4 }) == 2);
    System.out.println(s.jump(new int[] { 0 }) == 0);

  }
}

🔑 Key Variables

jumps: - Count of range extensions - Number of times we've "jumped" - The answer we return

currentEnd: - Fence/boundary of current range - When i reaches this, we must jump - Marks end of positions reachable with current jumps

furthest: - Scout exploring ahead - Maximum position reachable with one more jump - Becomes new currentEnd when we jump

Why Greedy Works:

At each range, explore ALL positions
Find FURTHEST reachable position
Extend range to furthest
Count extensions = count jumps

Greedy choice (furthest) = optimal choice!
Guarantees minimum jumps! ✓

🎪 Memory Aid

"Think in ranges, not positions!"
"Count the waves!"
"Jump at the fence!"
"Scout finds furthest!" ✨

Happy practicing! 🎯💪✨

Note: This problem demonstrates the complete optimization journey from exponential brute force through DP to optimal greedy! You learned: (1) FIVE different approaches with complete implementations, (2) WHY each works and their trade-offs, (3) Range-based greedy thinking (core insight), (4) How BFS naturally solves minimum steps problems, (5) Connection to Jump Game I. The detailed walkthroughs show exact variable states at each step - true mastery through comprehensive understanding! 💪✨🏆

288. Jump Game II

Problem Statement

🌳 Visual Understanding - The Jump Problem

The Problem We're Solving:

Understanding "Minimum Jumps":

All Possible Paths:

Difference from Jump Game I:

🧠 The AHA Moment - Why Dynamic Programming?

Key Observation:

Why Dynamic Programming?

🔴 Approach 1: Brute Force (Recursion)

📐 Function Definition

💡 Intuition

📝 Implementation

🔍 Dry Run Example: nums = [2, 3, 1, 1, 4]

📊 Complexity Analysis

🟡 Approach 2: Top-Down DP (Memoization)

📐 Function Definition

💡 Intuition

📝 Implementation

🔍 Detailed Dry Run: nums = [2, 3, 1, 1, 4]

📊 Complexity Analysis

🟢 Approach 3: Bottom-Up DP

📐 Function Definition

💡 Intuition

📝 Implementation

🔍 Detailed Dry Run: nums = [2, 3, 1, 1, 4]

📊 Complexity Analysis

🔵 Approach 4: BFS (Level-by-Level) - The Most Intuitive!

🎨 Building Intuition - Why BFS is Natural

📚 Real-World Analogy: The Party Invitation

🎯 Connecting to Jump Game

🌊 The Wave Analogy - Most Intuitive!

📝 BFS Implementation - With Human Thinking

🔍 Complete Visual Walkthrough - Like Telling a Story

💡 Why BFS is Perfect for This Problem

📊 Complexity Analysis

🟣 Approach 5: Greedy (Optimal Solution)

🎨 Understanding Greedy - Simple and Clear

The Simple Question

The Key Observation

Building Understanding Step by Step

The Pattern

The Two Simple Numbers We Track

Putting It Together

Visual Walkthrough

The Code - Now You Understand It

Why This Works - Simple Proof

Comparison: BFS vs Greedy

The Key Insight

Complete Example Walkthrough

Practice Problem

Complexity Analysis

Summary - The Simple Truth

📊 Approach Comparison

💡 Key Learnings

⚠️ Common Mistakes

🎉 Congratulations!

What You Learned:

The Beautiful Journey:

Pattern Evolution:

🎯 Pattern Recognition - Minimum Steps Problems

Core Pattern: BFS/Greedy Range Extension

Similar Problems:

🎓 Practice Exercise - Trace It Yourself!

✅ Solution to Practice Exercise

⚠️ Important Edge Cases to Test

📝 Quick Revision Notes

🎯 Core Concept

⚡ Quick Implementation - Greedy (Optimal)

🔑 Key Variables

🎪 Memory Aid