208. Jump Game

🔗 LeetCode Problem: 55. Jump Game
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Array, Greedy, 1D DP

Problem Statement

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: 
  Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: 
  You will always arrive at index 3 no matter what. 
  Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints: - 1 <= nums.length <= 10^4 - 0 <= nums[i] <= 10^5

🌳 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 (value = 2)
Goal: Reach index 4 (last index)

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

Question: Can we reach the last index? 🤔

Understanding Jump Lengths:

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

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

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

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

At index 3 (value = 1):
  Can jump: 1 step
  Reachable indices: 4 ✓

At index 4 (value = 4):
  Already at end! ✓

All Possible Paths for Example 1:

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

Path 1: 0 → 1 → 4
━━━━━━━━━━━━━━━━━━
  Start: index 0
  Jump 1 step → index 1
  Jump 3 steps → index 4 ✓

Path 2: 0 → 1 → 2 → 3 → 4
━━━━━━━━━━━━━━━━━━━━━━━━━
  Start: index 0
  Jump 1 step → index 1
  Jump 1 step → index 2
  Jump 1 step → index 3
  Jump 1 step → index 4 ✓

Path 3: 0 → 2 → 3 → 4
━━━━━━━━━━━━━━━━━━━━━━
  Start: index 0
  Jump 2 steps → index 2
  Jump 1 step → index 3
  Jump 1 step → index 4 ✓

Multiple paths exist! Answer: true ✓

Failed Example (Example 2):

nums = [3, 2, 1, 0, 4]
Index:  0  1  2  3  4

Trying all paths:

Path 1: 0 → 1 → ... ?
  Index 0: jump 1 → index 1 (value=2)
  Index 1: jump 1 → index 2 (value=1)
  Index 2: jump 1 → index 3 (value=0) ⚠️
  Index 3: value=0 → STUCK! Cannot jump! ❌

Path 2: 0 → 2 → ... ?
  Index 0: jump 2 → index 2 (value=1)
  Index 2: jump 1 → index 3 (value=0) ⚠️
  Index 3: value=0 → STUCK! Cannot jump! ❌

Path 3: 0 → 3 → ... ?
  Index 0: jump 3 → index 3 (value=0) ⚠️
  Index 3: value=0 → STUCK! Cannot jump! ❌

All paths lead to index 3 (the TRAP!)
Cannot reach index 4! Answer: false ❌

Visual:
  [3, 2, 1, 0, 4]
            ↑
          TRAP!
  Every path gets stuck at index 3!

🧠 The AHA Moment - Why Dynamic Programming?

Key Observation:

To know if we can reach the last index:
  - We need to know if we can reach intermediate indices
  - If we can reach index i, check all jumps from i

Recursive thinking:
  canReach(lastIndex) = true if we can reach any index j where:
    - j < lastIndex
    - canReach(j) = true
    - j + nums[j] >= lastIndex (can jump from j to last)

This is a reachability problem! 🎯

Why Not Greedy?

Initial thought: "Always jump the maximum distance"

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

Greedy approach:
  At index 0: jump max (2 steps) → index 2
  At index 2: jump max (1 step) → index 3
  At index 3: jump max (1 step) → index 4 ✓

Greedy works here! But...

Counter-example: nums = [5, 4, 0, 2, 0, 1, 0, 1, 0]

Greedy:
  At index 0: jump max (5 steps) → index 5 (value=1)
  At index 5: jump max (1 step) → index 6 (value=0)
  At index 6: STUCK! ❌

Optimal:
  At index 0: jump 1 step → index 1 (value=4)
  At index 1: jump 4 steps → index 5 → ... → index 8 ✓

Wait... actually for THIS problem, a modified greedy works!
But DP is more general and helps understand the structure! 🎯

Why Dynamic Programming?

1. OVERLAPPING SUBPROBLEMS:
   To check if we can reach index 5:
     - Check if we can reach 4, and jump from 4 to 5
     - Check if we can reach 3, and jump from 3 to 5
     - Check if we can reach 2, and jump from 2 to 5

   Many paths might revisit same indices! ⚠️

2. OPTIMAL SUBSTRUCTURE:
   canReach(n) depends on canReach(0), canReach(1), ..., canReach(n-1)

   If we can reach index i, and i + nums[i] >= n:
     → We can reach n! ✓

These properties = Perfect for DP! 🎯

Note: This problem also has an O(n) greedy solution!
But DP approach teaches the framework! 💡

🔴 Approach 1: Brute Force (Recursion)

📐 Function Definition

Function Signature:

boolean canJump(int[] nums)
boolean canJumpFromPosition(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 (boolean): - true = Can reach the last index FROM current position - false = Cannot reach the last index FROM current position - Example: canJumpFromPosition(0, nums) asks "can reach end from start?"

Purpose: - Check if we can reach last index from given position - Try all possible jump lengths from current position - Recursive exploration of all paths

Key Understanding:

canJumpFromPosition(2, [2,3,1,1,4]) asks:
  "Starting from index 2, can I reach index 4?"

Process:
  - At index 2, nums[2] = 1
  - Can jump 1 step → check canJumpFromPosition(3, nums)
  - If ANY jump reaches the end → return true

💡 Intuition

From current position, try ALL possible jumps:
  - Jump 1 step, 2 steps, 3 steps, ..., up to nums[position] steps
  - For each jump, check if we can reach the end from new position
  - If ANY jump works → return true
  - If NO jump works → return false

Base cases:
  - position == lastIndex: Already at end → return true
  - position >= nums.length: Out of bounds → return false

Recursion explores all possible paths!

📝 Implementation

class Solution {
    public boolean canJump(int[] nums) {
        return canJumpFromPosition(0, nums);
    }

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

        // Try all possible jumps from current position
        int maxJump = Math.min(position + nums[position], nums.length - 1);

        for (int nextPosition = position + 1; nextPosition <= maxJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) {
                return true;  // Found a path to the end!
            }
        }

        // No jump from this position can reach the end
        return false;
    }
}

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

canJumpFromPosition(0, [2,3,1,1,4])
├─ position=0, nums[0]=2, lastIndex=4
├─ maxJump = min(0+2, 4) = 2
├─ Try jumps: 1, 2
│
├─ Try nextPosition=1:
│  ├─ canJumpFromPosition(1, nums)
│  │  ├─ position=1, nums[1]=3, lastIndex=4
│  │  ├─ maxJump = min(1+3, 4) = 4
│  │  ├─ Try jumps: 2, 3, 4
│  │  │
│  │  ├─ Try nextPosition=2:
│  │  │  ├─ canJumpFromPosition(2, nums)
│  │  │  │  ├─ position=2, nums[2]=1, lastIndex=4
│  │  │  │  ├─ maxJump = min(2+1, 4) = 3
│  │  │  │  ├─ Try jump: 3
│  │  │  │  │
│  │  │  │  ├─ Try nextPosition=3:
│  │  │  │  │  ├─ canJumpFromPosition(3, nums)
│  │  │  │  │  │  ├─ position=3, nums[3]=1, lastIndex=4
│  │  │  │  │  │  ├─ maxJump = min(3+1, 4) = 4
│  │  │  │  │  │  ├─ Try jump: 4
│  │  │  │  │  │  │
│  │  │  │  │  │  ├─ Try nextPosition=4:
│  │  │  │  │  │  │  └─ position=4 == lastIndex → return true ✓
│  │  │  │  │  │  │
│  │  │  │  │  │  └─ return true
│  │  │  │  │  │
│  │  │  │  │  └─ return true
│  │  │  │  │
│  │  │  │  └─ return true
│  │  │  │
│  │  │  └─ return true
│  │  │
│  │  └─ return true (found path!)
│  │
│  └─ return true
│
└─ return true

Result: true ✓ (can reach last index)

📊 Complexity Analysis

Time Complexity: O(2^n)

At each position, try multiple jumps
Each creates a branch in recursion tree
Worst case: exponential branches

For nums = [1,1,1,1,1]:
  Position 0 → try 1
  Position 1 → try 1
  ...
  Creates long chain, but with backtracking

For nums = [n,n,n,...]:
  Each position tries n jumps
  Exponential explosion! 💥

Space Complexity: O(n)

Recursion stack depth = n (worst case)
Maximum n calls on stack at once

Why This Fails:

❌ Exponential time - too slow for n=10^4
❌ Recalculates same positions many times
❌ Times out on large inputs
✅ But shows the recursive structure!

🟡 Approach 2: Top-Down (Memoization)

📐 Function Definition

Function Signature:

boolean canJumpFromPosition(int position, int[] nums, Boolean[] memo)

What it represents:

Input Parameter position: - Current index in the array - Starting point for this subproblem - Example: position=3 means "currently at index 3"

Input Parameter nums: - The jump array - Unchanged throughout recursion

Input Parameter memo: - Memoization cache (array of size n) - memo[i] = can we reach the end FROM index i? - null = not yet calculated - true = can reach end from index i - false = cannot reach end from index i

Return Value (boolean): - true = Can reach last index FROM position - false = Cannot reach last index FROM position

Purpose: - Same as brute force BUT with caching - Store results to avoid recalculation - Each position calculated at most once

Key Understanding:

canJumpFromPosition(2, nums, memo) asks:
  "Can I reach the end from index 2?"

First call:
  - memo[2] = null (not calculated)
  - Calculate the answer
  - Store in memo[2]
  - Return result

Second call:
  - memo[2] already has answer
  - Return immediately (no recalculation!)

💡 Intuition - The Clever Conversion

PROBLEM IDENTIFIED in Brute Force:
  Same positions checked multiple times

SOLUTION:
  Cache results the FIRST time we calculate them
  Next time → instant lookup! 🎯

HOW TO IDENTIFY WHAT TO MEMOIZE:
  1. Function parameter: position
  2. Same position always gives same answer
  3. Memoize using position as key
  4. Key range: 0 to n-1

CONVERSION FROM BRUTE FORCE:
  1. Add memo array: Boolean[n]
  2. Check cache before calculating
  3. Store result before returning
  4. Same logic, just add caching!

🎯 Base Cases Transformation

BRUTE FORCE BASE CASES:
  if (position == nums.length - 1) return true;

TOP-DOWN BASE CASES (SAME!):
  if (position == nums.length - 1) return true;

Why same?
  - Base case: "already at the end"
  - Memoization doesn't change the logic

ONLY ADDITIONS:
  1. Create memo array: Boolean[n]
  2. Check memo[position] before calculating
  3. Store memo[position] before returning

📝 Implementation

class Solution {
    public boolean canJump(int[] nums) {
        Boolean[] memo = new Boolean[nums.length];
        return canJumpFromPosition(0, nums, memo);
    }

    private boolean canJumpFromPosition(int position, int[] nums, Boolean[] memo) {
        // Base case: reached the last index
        if (position == nums.length - 1) {
            return true;
        }

        // Check if already calculated
        if (memo[position] != null) {
            return memo[position];  // Cache HIT!
        }

        // Try all possible jumps from current position
        int maxJump = Math.min(position + nums[position], nums.length - 1);

        for (int nextPosition = position + 1; nextPosition <= maxJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums, memo)) {
                memo[position] = true;  // Store before returning
                return true;
            }
        }

        // No jump from this position can reach the end
        memo[position] = false;  // Store before returning
        return false;
    }
}

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

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

Initial State:
memo = [null, null, null, null, null]
        ↑     ↑     ↑     ↑     ↑
        0     1     2     3     4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call: canJumpFromPosition(0, nums, memo)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 1: position=0
  Not at end (0 ≠ 4)
  memo[0] = null → CACHE MISS
  maxJump = min(0+2, 4) = 2
  Try positions: 1, 2

  Try position=1 → canJumpFromPosition(1, nums, memo)

Step 2: position=1
  Not at end (1 ≠ 4)
  memo[1] = null → CACHE MISS
  maxJump = min(1+3, 4) = 4
  Try positions: 2, 3, 4

  Try position=2 → canJumpFromPosition(2, nums, memo)

Step 3: position=2
  Not at end (2 ≠ 4)
  memo[2] = null → CACHE MISS
  maxJump = min(2+1, 4) = 3
  Try positions: 3

  Try position=3 → canJumpFromPosition(3, nums, memo)

Step 4: position=3
  Not at end (3 ≠ 4)
  memo[3] = null → CACHE MISS
  maxJump = min(3+1, 4) = 4
  Try positions: 4

  Try position=4 → canJumpFromPosition(4, nums, memo)

Step 5: position=4
  position == lastIndex (4 == 4) → BASE CASE
  Return true

  Back to Step 4

Step 6: Back at position=3
  Got true from position=4
  Store: memo[3] = true ✓
  Return true

  memo = [null, null, null, true, null]

  Back to Step 3

Step 7: Back at position=2
  Got true from position=3
  Store: memo[2] = true ✓
  Return true

  memo = [null, null, true, true, null]

  Back to Step 2

Step 8: Back at position=1
  Got true from position=2
  Store: memo[1] = true ✓
  Return true

  memo = [null, true, true, true, null]

  Back to Step 1

Step 9: Back at position=0
  Got true from position=1
  Store: memo[0] = true ✓
  Return true

  Final memo = [true, true, true, true, null]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: true (can reach last index) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Understanding memo:
  memo[0] = true → "Can reach end from index 0"
  memo[1] = true → "Can reach end from index 1"
  memo[2] = true → "Can reach end from index 2"
  memo[3] = true → "Can reach end from index 3"
  memo[4] = null → "Never checked (already at end)"

📊 Complexity Analysis

Time Complexity: O(n²)

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

Much better than O(2^n)! 🚀

Space Complexity: O(n)

Memoization array: O(n)
Recursion stack: O(n)
Total: O(n) + O(n) = O(n)

🟢 Approach 3: Bottom-Up (Tabulation)

📐 Function Definition

DP Array Definition:

boolean[] dp = new boolean[n];

What dp[i] represents:

Index i: - Position in the array - Example: i=2 means "index 2"

Value dp[i] (boolean): - dp[i] = true → Can reach the LAST index FROM index i - dp[i] = false → Cannot reach the LAST index FROM index i - Example: dp[0] = true means "can reach end from start"

Purpose: - Store reachability for each position - Build from end to start (backwards) - Bottom-up: start from last index, build to index 0

Key Understanding:

dp[3] = true means:
  "Starting from index 3, I CAN reach the last index"

dp[2] = false means:
  "Starting from index 2, I CANNOT reach the last index"

Building backwards ensures we know reachability
of later positions before checking earlier ones!

💡 Intuition - The Clever Conversion from Top-Down

TOP-DOWN (Recursion + Memoization):
  Start from index 0 → recurse forward → cache results

BOTTOM-UP (Iteration + Tabulation):
  Start from last index → iterate backwards to index 0

  dp[n-1] = true (already at end)
    ↓ build backwards
  dp[n-2] = can jump to any dp[j]=true where j > n-2?
    ↓ build backwards
  dp[n-3] = can jump to any dp[j]=true where j > n-3?
    ↓ build backwards
  ...
    ↓ build backwards
  dp[0] = answer!

  Direction: END → backwards to START

WHY BACKWARDS?
  To check if we can reach end from position i:
    - Need to know reachability of positions i+1, i+2, ...
    - Build from end ensures later positions are ready!

🎯 Base Cases Transformation - VERY IMPORTANT! 🔑

TOP-DOWN BASE CASES (in recursion):
  if (position == n-1) return true;

  Termination condition: "reached the end"

BOTTOM-UP BASE CASES (in DP table):
  dp[n-1] = true;

  Initialization: "last position is reachable from itself"

KEY INSIGHT - THE CLEVER THINKING:
  1. Top-down: "When do I stop recursing?"
     → At last index, return true

  2. Bottom-up: "What's the known base case?"
     → dp[n-1] = true, build backwards

  3. Same value (true), different role:
     - Top-down: where recursion STOPS
     - Bottom-up: where iteration STARTS

🔄 Recurrence Relation

Definition:
  dp[i] = can we reach the last index FROM index i?

For position i:
  - Can jump 1, 2, ..., nums[i] steps
  - Check all reachable positions j = i+1, i+2, ..., i+nums[i]
  - If ANY dp[j] = true → dp[i] = true

Formula:
  dp[i] = true  if EXISTS j: (i < j <= i+nums[i]) AND dp[j]=true
  dp[i] = false otherwise

Dependencies:
  dp[i] depends on dp[i+1], dp[i+2], ..., dp[n-1]
  (all positions reachable from i)

Must build BACKWARDS: n-1, n-2, ..., 1, 0

📝 Implementation

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;

        // Create DP table
        // dp[i] = can we reach the end FROM index i?
        boolean[] dp = new boolean[n];

        // Base case: last position is reachable from itself
        dp[n - 1] = true;

        // Build backwards from second-last to first
        for (int i = n - 2; i >= 0; i--) {
            // Check all positions we can jump to from i
            int farthestJump = Math.min(i + nums[i], n - 1);

            for (int j = i + 1; j <= farthestJump; j++) {
                if (dp[j]) {
                    dp[i] = true;  // Found reachable position!
                    break;  // No need to check further
                }
            }
        }

        // Answer: can we reach end from start?
        return dp[0];
    }
}

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

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

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

Create DP table:
dp = [false, false, false, false, false]
      ↑      ↑      ↑      ↑      ↑
      0      1      2      3      4

Base case:
dp[4] = true  (last position reachable from itself)

dp = [false, false, false, false, true]
                                  ↑
                              base case ✓

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

Iteration 1: i = 3
━━━━━━━━━━━━━━━━
Position 3, nums[3] = 1
Can jump 1 step
farthestJump = min(3+1, 4) = 4

Check positions: 4
  dp[4] = true ✓ Found reachable position!

dp[3] = true

dp = [false, false, false, true, true]


Iteration 2: i = 2
━━━━━━━━━━━━━━━━
Position 2, nums[2] = 1
Can jump 1 step
farthestJump = min(2+1, 4) = 3

Check positions: 3
  dp[3] = true ✓ Found reachable position!

dp[2] = true

dp = [false, false, true, true, true]


Iteration 3: i = 1
━━━━━━━━━━━━━━━━
Position 1, nums[1] = 3
Can jump 1, 2, or 3 steps
farthestJump = min(1+3, 4) = 4

Check positions: 2, 3, 4
  dp[2] = true ✓ Found reachable position!

dp[1] = true

dp = [false, true, true, true, true]


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

Check positions: 1, 2
  dp[1] = true ✓ Found reachable position!

dp[0] = true

Final DP table:
dp = [true, true, true, true, true]
      ↑
   ANSWER!

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

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

Meaning of each value:
  dp[0] = true → "Can reach end from index 0" ✓
  dp[1] = true → "Can reach end from index 1" ✓
  dp[2] = true → "Can reach end from index 2" ✓
  dp[3] = true → "Can reach end from index 3" ✓
  dp[4] = true → "Already at end" (base case)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: true (can reach last index from start) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

📊 Complexity Analysis

Time Complexity: O(n²)

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

Space Complexity: O(n)

DP table of size n: O(n)
No recursion stack: O(1)
Total: O(n)

🔵 Approach 4: Space-Optimized (Greedy)

📐 Function Definition

Function Signature:

boolean canJump(int[] nums)

What it represents:

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

Return Value (boolean): - true = Can reach the last index from start - false = Cannot reach the last index from start

Purpose: - Instantly determine reachability using greedy approach - Track the farthest position reachable - O(n) time, O(1) space solution

Key Understanding:

Instead of checking every position:
  Track maxReach = farthest index we can reach

At each position i:
  - If i > maxReach → unreachable → return false
  - Update maxReach = max(maxReach, i + nums[i])

If maxReach >= lastIndex at any point → return true

Greedy: Always track maximum reach possible!

💡 Intuition - Greedy Optimization

KEY INSIGHT from DP:
  We only care if we CAN reach the end
  Don't need to know exact path!

GREEDY IDEA:
  Track the farthest position we can reach

  maxReach = maximum index reachable so far

  At each position i:
    - If i > maxReach → can't reach this position → return false
    - Update: maxReach = max(maxReach, i + nums[i])
    - If maxReach >= lastIndex → found path → return true

WHY THIS WORKS:
  If we can reach position i:
    - We explored all positions 0 to i
    - maxReach represents farthest we can go
    - If maxReach >= lastIndex → we win!

  If we can't reach position i:
    - i > maxReach means there's a gap
    - No way to reach i or beyond → return false

OPTIMIZATION:
  - No DP table needed
  - Single pass through array
  - O(1) space! 🚀

📝 Implementation

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int maxReach = 0;  // Farthest position we can reach

        for (int i = 0; i < n; i++) {
            // If current position is beyond max reach → unreachable
            if (i > maxReach) {
                return false;
            }

            // Update max reach from current position
            maxReach = Math.max(maxReach, i + nums[i]);

            // Early exit: if we can reach or pass the last index
            if (maxReach >= n - 1) {
                return true;
            }
        }

        return true;
    }
}

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

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

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

maxReach = 0  (initially can only reach index 0)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Iteration 1: i = 0
━━━━━━━━━━━━━━━━
Position 0, nums[0] = 2

Check: i (0) > maxReach (0)? No ✓ (can reach this position)

Update maxReach:
  maxReach = max(0, 0 + 2) = 2

Check: maxReach (2) >= lastIndex (4)? No

State: maxReach = 2
Meaning: "Can reach up to index 2"


Iteration 2: i = 1
━━━━━━━━━━━━━━━━
Position 1, nums[1] = 3

Check: i (1) > maxReach (2)? No ✓ (can reach this position)

Update maxReach:
  maxReach = max(2, 1 + 3) = 4

Check: maxReach (4) >= lastIndex (4)? Yes! ✓

Early exit: We can reach the last index!

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: true (can reach last index) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Why we stopped early:
  At index 1, we discovered maxReach = 4
  This means we can reach index 4 (the end)
  No need to check remaining positions!

🔍 Dry Run - Failing Case: nums = [3, 2, 1, 0, 4]

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

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

maxReach = 0

Iteration 1: i = 0
  nums[0] = 3
  i (0) <= maxReach (0) ✓
  maxReach = max(0, 0+3) = 3
  maxReach (3) < lastIndex (4)

Iteration 2: i = 1
  nums[1] = 2
  i (1) <= maxReach (3) ✓
  maxReach = max(3, 1+2) = 3
  maxReach (3) < lastIndex (4)

Iteration 3: i = 2
  nums[2] = 1
  i (2) <= maxReach (3) ✓
  maxReach = max(3, 2+1) = 3
  maxReach (3) < lastIndex (4)

Iteration 4: i = 3
  nums[3] = 0
  i (3) <= maxReach (3) ✓
  maxReach = max(3, 3+0) = 3
  maxReach (3) < lastIndex (4)

Iteration 5: i = 4
  i (4) > maxReach (3)? Yes! ❌
  Cannot reach position 4!

Return false

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: false (cannot reach last index) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Why it failed:
  maxReach stuck at 3 (the trap position)
  Position 3 has value 0 → can't jump further
  Position 4 is beyond maxReach → unreachable!

📊 Complexity Analysis

Time Complexity: O(n)

Single pass through array
Each position visited once
Total: O(n) ✓

MASSIVE improvement from O(n²)! 🚀

Space Complexity: O(1)

Only one variable: maxReach
No array, no recursion
Constant space! ✓

Improvement from O(n) to O(1)! 🚀

🎨 Building Greedy Intuition - Step by Step

Let's understand WHY greedy works through discovery, not just code!

The Core Question We're Asking:

Instead of asking: "Can I reach the END from position i?"
Ask this instead:  "What's the FURTHEST I can possibly reach?"

This mindset shift is KEY! 🔑

Visual Discovery - Example 1

nums = [2, 3, 1, 1, 4]
Index:  0  1  2  3  4

Let's track "furthest reachable position" as we scan left to right:

┌─────────────────────────────────────────────────────────────┐
│ POSITION 0                                                  │
└─────────────────────────────────────────────────────────────┘

At index 0:
  Value: 2
  Can jump: 1 or 2 steps
  Reachable: indices 1, 2

  furthest = 0 + 2 = 2

Visual:
  [0, 1, 2, 3, 4]
   ↑  ←─┘
   |_____|
   Can reach up to here!

┌─────────────────────────────────────────────────────────────┐
│ POSITION 1                                                  │
└─────────────────────────────────────────────────────────────┘

At index 1:
  Value: 3
  Can jump: 1, 2, or 3 steps
  From index 1, can reach: 2, 3, 4

  Calculate: 1 + 3 = 4

  furthest = max(2, 4) = 4 ✓

Visual:
  [0, 1, 2, 3, 4]
   ↑     ←─────┘
   |___________|
   Extended our reach to the END!

Key insight: 
  Position 1 is WITHIN our reach (1 ≤ 2)
  From position 1, we can extend reach to 4
  Since 4 is the last index → WE CAN REACH THE END! ✓

We don't need to check positions 2, 3, 4 anymore!
Already know we can reach them!

Result: true ✓

Understanding "furthest"

Think of it like a FLASHLIGHT:

At each position, our flashlight shines further or stays same:

Position 0: [████░░░░]  (can see up to index 2)
Position 1: [████████]  (can see up to index 4 - THE END!)

The key questions:
1. "Can I reach this position?" → Is position ≤ furthest?
2. "From here, how far can my light extend?" → position + nums[position]
3. "Did I reach the end?" → Is furthest ≥ lastIndex?

That's it! Three simple checks! 🎯

Why This Works - The "NO GAPS" Property

CRITICAL INSIGHT:

If furthest = 5, it means:
  ✓ We can reach index 0 (start)
  ✓ We can reach index 1
  ✓ We can reach index 2  
  ✓ We can reach index 3
  ✓ We can reach index 4
  ✓ We can reach index 5

We can reach ALL positions from 0 to furthest!

Why? Because:
  - We started at 0
  - At each position i (where i ≤ furthest), we checked jumps
  - We updated furthest to maximum possible
  - This creates a CONTINUOUS REACHABLE RANGE with NO GAPS!

If there was a gap:
  Some position i would be > furthest
  We'd detect it and return false immediately!

Visual Discovery - Example 2 (Failure Case)

nums = [3, 2, 1, 0, 4]
Index:  0  1  2  3  4

Let's trace furthest:

┌─────────────────────────────────────────────────────────────┐
│ POSITION 0                                                  │
└─────────────────────────────────────────────────────────────┘

At index 0:
  Value: 3
  furthest = 0 + 3 = 3

Visual:
  [0, 1, 2, 3, 4]
   ↑  ←─────┘
   Can reach up to index 3

┌─────────────────────────────────────────────────────────────┐
│ POSITION 1                                                  │
└─────────────────────────────────────────────────────────────┘

Check: Is 1 ≤ furthest(3)? YES ✓ (reachable)

At index 1:
  Value: 2
  Calculate: 1 + 2 = 3
  furthest = max(3, 3) = 3 (no improvement)

Visual:
  [0, 1, 2, 3, 4]
   ↑  ←─────┘
   Still stuck at index 3

┌─────────────────────────────────────────────────────────────┐
│ POSITION 2                                                  │
└─────────────────────────────────────────────────────────────┘

Check: Is 2 ≤ furthest(3)? YES ✓ (reachable)

At index 2:
  Value: 1
  Calculate: 2 + 1 = 3
  furthest = max(3, 3) = 3 (no improvement)

┌─────────────────────────────────────────────────────────────┐
│ POSITION 3                                                  │
└─────────────────────────────────────────────────────────────┐

Check: Is 3 ≤ furthest(3)? YES ✓ (barely reachable)

At index 3:
  Value: 0 ⚠️
  Calculate: 3 + 0 = 3
  furthest = max(3, 3) = 3 (STUCK!)

Visual:
  [0, 1, 2, 3 | 4]
   ←─────────┘ ↑
   Can reach    TRAP! Can't reach here!

┌─────────────────────────────────────────────────────────────┐
│ POSITION 4                                                  │
└─────────────────────────────────────────────────────────────┘

Check: Is 4 ≤ furthest(3)? NO! ❌

Position 4 is BEYOND our furthest reach!
There's a GAP - we can't get to position 4!

Result: false ✗

The TRAP at index 3 (value=0) prevented us from going further!

The "Maximum Reach" Analogy

Think of it like EXPLORING A MAP:

Starting Position: You're at city 0
Goal: Reach city (n-1)

At each city you visit:
  - You get a MAP showing how far you can travel from there
  - You keep track of the FURTHEST city you know you can reach
  - You visit each city in order (0, 1, 2, ...)

Rules:
  1. If next city is beyond your "known furthest":
     → You CAN'T reach it (there's a gap in your map!)
     → Return false

  2. If you can reach a city:
     → Check its map
     → Update your "known furthest" if this city's map extends further

  3. If "known furthest" reaches or passes the goal:
     → You WIN! Return true

This is EXACTLY what the greedy algorithm does! 🗺️

Why We Don't Need DP's Detailed Tracking

DP Approach:
  dp[0] = Can reach end from 0? → Check all paths → YES
  dp[1] = Can reach end from 1? → Check all paths → YES
  dp[2] = Can reach end from 2? → Check all paths → YES
  dp[3] = Can reach end from 3? → Check all paths → YES
  dp[4] = At end already → YES

  Stores: 5 booleans
  Checks: Many paths from each position

Greedy Approach:
  furthest = Maximum index reachable so far

  Just one number! And it tells us EVERYTHING:

  furthest = 5 means:
    ✓ Can reach end (5 ≥ 4)
    ✓ Can reach ALL positions 0,1,2,3,4,5
    ✓ Don't need to know HOW, just that we CAN!

The beauty: We only care about REACHABILITY, not PATHS!
Greedy is sufficient! ✨

🎯 The Complete Greedy Algorithm - Intuitive Version

class Solution {
    public boolean canJump(int[] nums) {
        // Track the furthest position we can possibly reach
        int furthest = 0;

        // Check each position in order
        for (int i = 0; i < nums.length; i++) {

            // CRITICAL CHECK: Can we even reach this position?
            // If current position is beyond our furthest reach → GAP exists!
            if (i > furthest) {
                return false;  // Stuck! Can't proceed!
            }

            // We can reach position i (because i ≤ furthest)
            // From position i, we can jump up to nums[i] steps
            // So from i, we can reach up to: i + nums[i]

            // Update our furthest reachable position
            furthest = Math.max(furthest, i + nums[i]);
            //              ↑              ↑
            //         old furthest   new possibility from position i

            // OPTIMIZATION: Early exit if we can already reach the end
            if (furthest >= nums.length - 1) {
                return true;  // Success! We can reach the end!
            }
        }

        // If we checked all positions and didn't find a gap
        // Check if our furthest reach includes the last index
        return furthest >= nums.length - 1;
    }
}

🔍 Detailed Walkthrough with Every Variable

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

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

furthest = 0

Meaning: "Right now, I can only reach index 0 (where I start)"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
LOOP ITERATION 1: i = 0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Question 1: Can I reach position 0?
  Check: i (0) > furthest (0)? 
  Answer: NO (0 is not > 0)
  Conclusion: ✓ I can reach position 0 (I start here!)

At position 0:
  nums[0] = 2

Question 2: From position 0, how far can I jump?
  Maximum jump: i + nums[i] = 0 + 2 = 2

Update furthest:
  furthest = max(0, 2) = 2

  New understanding: "I can now reach up to index 2!"

Question 3: Did I reach the end?
  Check: furthest (2) >= lastIndex (4)?
  Answer: NO (2 < 4)
  Conclusion: Keep searching!

State after iteration 1:
  furthest = 2
  Reachable positions: [0, 1, 2]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
LOOP ITERATION 2: i = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Question 1: Can I reach position 1?
  Check: i (1) > furthest (2)?
  Answer: NO (1 ≤ 2)
  Conclusion: ✓ Position 1 is within my reach!

At position 1:
  nums[1] = 3

Question 2: From position 1, how far can I jump?
  Maximum jump: i + nums[i] = 1 + 3 = 4

Update furthest:
  furthest = max(2, 4) = 4

  New understanding: "I can now reach up to index 4!"

Question 3: Did I reach the end?
  Check: furthest (4) >= lastIndex (4)?
  Answer: YES! (4 = 4) ✓

  EARLY EXIT: Return true!

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: true
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

We discovered we can reach the end at iteration 2!
Didn't need to check positions 2, 3, 4!

Visual of reachability:
  Position 0: furthest=2  → [0,1,2]░░
  Position 1: furthest=4  → [0,1,2,3,4] ✓ REACHED END!

🎨 Visual Understanding - The Expanding Window

Think of "furthest" as an EXPANDING WINDOW:

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

Initial:
  [•]░░░░  furthest=0 (only at start)

After position 0 (value=2):
  [•••]░░  furthest=2 (expanded window!)
   0 1 2

After position 1 (value=3):
  [•••••]  furthest=4 (window reached end!)
   0 1 2 3 4 ✓ DONE!

If position 3 was beyond window:
  [••• ? ]  Can't reach position 3!
   0 1 2 3   Gap! Return false!

The window MUST be continuous!
Any gap means unreachable!

💡 The "AHA!" Moment

THE KEY INSIGHT:

You don't need to know the EXACT PATH to the end!
You just need to know IF you can reach there!

DP asks: "What's the path?"
Greedy asks: "Can I reach that far?"

Example:
  Position 0 → can reach positions [1, 2]
  Position 1 → can reach positions [2, 3, 4]

  DP: Stores "from 0 can reach end" and "from 1 can reach end"
  Greedy: Stores "furthest reachable = 4" (which is ≥ end)

  Same answer, but greedy is:
    ✓ Simpler (one number vs. array)
    ✓ Faster (one pass vs. checking all jumps)
    ✓ Less memory (O(1) vs. O(n))

This is the power of asking the RIGHT QUESTION! 🎯

🔄 Comparing with DP to Build Intuition

Same Example: nums = [2, 3, 1, 1, 4]

DP THINKING (Backwards):
━━━━━━━━━━━━━━━━━━━━━
dp[4] = true  (base case: at end)
dp[3] = true  (can jump to dp[4])
dp[2] = true  (can jump to dp[3])
dp[1] = true  (can jump to dp[2], dp[3], dp[4])
dp[0] = true  (can jump to dp[1] or dp[2])

Stores: 5 values
Checks: Multiple positions from each index

GREEDY THINKING (Forward):
━━━━━━━━━━━━━━━━━━━━━━━
furthest starts at 0
At i=0: furthest becomes 2  (can reach [0,1,2])
At i=1: furthest becomes 4  (can reach [0,1,2,3,4]) ✓ DONE!

Stores: 1 value
Checks: Each position once

SAME RESULT, but greedy is simpler and faster!

Why can greedy be simpler?
  Because we only need YES/NO answer!
  We don't need to track WHICH positions can reach end
  Just need to know IF end is reachable!

  "furthest ≥ end" tells us everything! ✨

🎓 Practice Exercise - Trace It Yourself!

Try this example yourself: nums = [1, 2, 0, 1]

Step 1: Initialize furthest = 0

Step 2: Process each position:

Position 0:
  Can reach? _____
  nums[0] = _____
  furthest = max(_____, 0 + _____) = _____
  Reached end? _____

Position 1:
  Can reach? _____
  nums[1] = _____
  furthest = max(_____, 1 + _____) = _____
  Reached end? _____

Position 2:
  Can reach? _____
  nums[2] = _____
  furthest = max(_____, 2 + _____) = _____
  Reached end? _____

Position 3:
  Can reach? _____
  Result: _____

Solution at the end of this section! (Don't peek!)

✅ Solution to Practice Exercise

nums = [1, 2, 0, 1]

furthest = 0

Position 0:
  Can reach? YES (0 ≤ 0)
  nums[0] = 1
  furthest = max(0, 0 + 1) = 1
  Reached end (3)? NO

Position 1:
  Can reach? YES (1 ≤ 1)
  nums[1] = 2
  furthest = max(1, 1 + 2) = 3
  Reached end (3)? YES! ✓

Result: true

We can reach the end!
Actual path: 0 → 1 → 3 (skip index 2)
But greedy doesn't need to know the path! Just knows it's possible!

🎯 Pattern Recognition - Reachability Problems

Core Pattern: Can We Reach Target?

Template for reachability problems:

Track maximum reachable position:
  maxReach = 0

  For each position i:
    - If i > maxReach → unreachable → fail
    - Update maxReach with jumps from i
    - If maxReach >= target → success

Key insight: Greedy tracking of farthest reach!

⚠️ Important Edge Cases to Test

// Minimum array size
nums = [0]           // Expected: true (already at end)
nums = [2]           // Expected: true (already at end)

// Cannot reach end
nums = [0,1]         // Expected: false (stuck at start)
nums = [1,0,1,0]     // Expected: false (stuck at index 1)
nums = [3,2,1,0,4]   // Expected: false (trap at index 3)

// Can reach end
nums = [2,3,1,1,4]   // Expected: true (multiple paths)
nums = [1,1,1,1]     // Expected: true (can hop to end)

// Large jumps
nums = [10,0,0,0]    // Expected: true (big jump over zeros)
nums = [0,10,0,0]    // Expected: false (can't start)

// All zeros except last
nums = [0,0,0,0]     // Expected: false (stuck at start)

// Maximum jump at each position
nums = [5,4,3,2,1,0] // Expected: true (greedy works)

📝 Quick Revision Notes

🎯 Core Concept

Problem: Given array where nums[i] = max jump length at position i, can we reach the last index from index 0?

Function Definitions: - canJumpFromPosition(i) = Can we reach the last index FROM position i? - dp[i] = Can we reach the last index FROM position i? - maxReach = Farthest index we can reach (greedy approach)

Key Insight: Track maximum reachable position. If any position is beyond maxReach, it's unreachable. Update maxReach greedily as we go.

Four Approaches: 1. Brute Force: Try all jump paths → O(2^n) time ❌ 2. Top-Down: Memoization → O(n²) time, O(n) space ✓ 3. Bottom-Up: DP table backwards → O(n²) time, O(n) space ✓ 4. Greedy: Track maxReach → O(n) time, O(1) space ⭐⭐⭐

⚡ Quick Implementation

public class Solution {
  public boolean canJump(int[] a) {
    // // Approach 1 - recursion
    // return recursive(0, a);

    // // Approach 2 - top down
    // Boolean[] memo = new Boolean[a.length + 1];
    // return topDown(0, a, memo);

    // Approach 3 - bottom up
    // return bottomUp(a);

    return greedy(a);
  }

  private boolean greedy(int[] a) {
    int n = a.length;
    int maxCanReach = 0;

    // step 1: start journey at every index
    for (int i = 0; i < n; i++) {
      // step 5: is that even possible if I can reach this index 'i'?
      if (i > maxCanReach) {
        // from earlier indices, we should be able to reach the current index
        return false;
      }

      // step 2: how much farthest i can reach from the current index
      maxCanReach = Math.max(maxCanReach, i + a[i]);

      // step 3: did i cross boundary. If yes, true
      if (maxCanReach >= n - 1) {
        return true;
      }
    }

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

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

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

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

      for (int step = 1; step <= a[index]; step++) {
        if (index + step <= n && dp[index + step]) {
          dp[index] = true;

          break;
        }

      }
    }

    return dp[0];
  }

  private boolean topDown(int index, int[] a, Boolean[] memo) {
    // base case
    if (index >= a.length - 1) {
      // Commented below line as sometimes index out of bounds can happen.
      // return memo[index] = true;
      return true;
    }

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

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

      if (topDown(index + step, a, memo)) {
        return memo[index] = true;
      }
    }

    // Above never returned true, so return false
    return memo[index] = false;
  }

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

    for (int step = 1; step <= a[index]; step++) {
      if (recursive(index + step, a)) {
        return true;
      }
    }

    // Above never returned true, so return false
    return false;
  }

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

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

    System.out.println(s.canJump(new int[] { 0 }) == true);
    System.out.println(s.canJump(new int[] { 2 }) == true);

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

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

    System.out.println(s.canJump(new int[] { 10, 0, 0, 0 }) == true);
    System.out.println(s.canJump(new int[] { 0, 10, 0, 0 }) == false);

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

🔑 Key Insights

Greedy Strategy:

maxReach = farthest position we can reach

At position i:
  - If i > maxReach → unreachable → return false
  - Update: maxReach = max(maxReach, i + nums[i])
  - If maxReach >= lastIndex → return true

Why greedy works:
  We only care IF we can reach end, not HOW
  Tracking max reach is sufficient!

DP vs Greedy:

DP Approach:
  - Checks each position explicitly
  - Stores reachability for all positions
  - O(n²) time, O(n) space

Greedy Approach:
  - Tracks only maximum reach
  - Single pass, no storage
  - O(n) time, O(1) space

Greedy is OPTIMAL for this problem! 🎯

🎪 Memory Aid

"Track max reach, not each position!"
"Can't reach position if beyond max!"
"Greedy beats DP here!"
"One pass, one variable!" ✨

⚠️ Common Mistakes

❌ Building DP table forwards instead of backwards
❌ Not checking if position i > maxReach (greedy)
❌ Forgetting early exit when maxReach >= lastIndex
❌ Using O(n²) DP when O(n) greedy exists
❌ Confusing "reach FROM i" vs "reach TO i"

✅ Interview Talking Points

"This is a reachability problem with optimal greedy solution.

Greedy Approach (Optimal):
  1. Track maxReach = farthest position reachable
  2. At each position i:
     - If i > maxReach → unreachable → return false
     - Update maxReach = max(maxReach, i + nums[i])
     - If maxReach >= lastIndex → return true

Why greedy works:
  - We only need to know IF we can reach end
  - Don't need to store paths or intermediate states
  - Maximum reach tells us everything we need

DP Alternative:
  - Build dp[i] = can reach end from i
  - Work backwards from last index
  - O(n²) time, O(n) space
  - Valid but not optimal

Complexity: Greedy is O(n) time, O(1) space
            DP is O(n²) time, O(n) space"

🎉 Congratulations!

You've mastered Jump Game - from DP to optimal greedy!

What You Learned:

✅ Reachability Problems - Can we reach target position?
✅ Bottom-Up DP - Building backwards from goal
✅ Greedy Optimization - Tracking maximum reach
✅ O(n²) to O(n) - From DP to greedy improvement
✅ Space Optimization - From O(n) to O(1)
✅ Early Exit Strategy - Stop when answer is found

The Beautiful Journey:

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

Top-Down DP (O(n²)):
  "Cache which positions can reach end"
  → Better! Polynomial time! 😊

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

Greedy (O(n)):
  "Just track maximum reachable position!"
  → Optimal! Linear time, constant space! 🚀⭐

Pattern Evolution:

Problem 205: Fibonacci Counting
Problem 206: Cost Optimization
Problem 207: Game Theory
Problem 208: Reachability + Greedy! 🎯

DP teaches us to think systematically
Greedy shows us when simpler solution exists!

You've now mastered both DP thinking AND greedy optimization! 🚀✨

208. Jump Game

Problem Statement

🌳 Visual Understanding - The Jump Problem

The Problem We're Solving:

Understanding Jump Lengths:

All Possible Paths for Example 1:

Failed Example (Example 2):

🧠 The AHA Moment - Why Dynamic Programming?

Key Observation:

Why Not Greedy?

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 (Memoization)

📐 Function Definition

💡 Intuition - The Clever Conversion

🎯 Base Cases Transformation

📝 Implementation

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

📊 Complexity Analysis

🟢 Approach 3: Bottom-Up (Tabulation)

📐 Function Definition

💡 Intuition - The Clever Conversion from Top-Down

🎯 Base Cases Transformation - VERY IMPORTANT! 🔑

🔄 Recurrence Relation

📝 Implementation

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

📊 Complexity Analysis

🔵 Approach 4: Space-Optimized (Greedy)

📐 Function Definition

💡 Intuition - Greedy Optimization

📝 Implementation

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

🔍 Dry Run - Failing Case: nums = [3, 2, 1, 0, 4]

📊 Complexity Analysis

🎨 Building Greedy Intuition - Step by Step

The Core Question We're Asking:

Visual Discovery - Example 1

Understanding "furthest"

Why This Works - The "NO GAPS" Property

Visual Discovery - Example 2 (Failure Case)

The "Maximum Reach" Analogy

Why We Don't Need DP's Detailed Tracking

🎯 The Complete Greedy Algorithm - Intuitive Version

🔍 Detailed Walkthrough with Every Variable

🎨 Visual Understanding - The Expanding Window

💡 The "AHA!" Moment

🔄 Comparing with DP to Build Intuition

🎓 Practice Exercise - Trace It Yourself!

✅ Solution to Practice Exercise

🎯 Pattern Recognition - Reachability Problems

Core Pattern: Can We Reach Target?

Similar Problems:

⚠️ Important Edge Cases to Test

📝 Quick Revision Notes

🎯 Core Concept

⚡ Quick Implementation

🔑 Key Insights

🎪 Memory Aid

⚠️ Common Mistakes

✅ Interview Talking Points

🎉 Congratulations!

What You Learned:

The Beautiful Journey:

Pattern Evolution: