Jump Game

• Difficulty: Medium
• Topics: Array, Dynamic Programming, Greedy
• Link: https://leetcode.com/problems/jump-game/

Problem Description

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 <= 104
• 0 <= nums[i] <= 105

Solution

1. Problem Deconstruction

Technical Restatement
Given a 0-indexed array nums where nums[i] specifies the maximum allowable forward jump from index i, determine if there exists a sequence of jumps starting at index 0 that terminates at the last index (nums.length - 1).

Beginner Explanation
Imagine standing on the first tile of a row of tiles. Each tile has a number telling you the farthest you can jump forward from it. Your goal is to reach the last tile. Decide if it’s possible by choosing jumps optimally.

Mathematical Formulation
Let f(i) represent the farthest index reachable from index i as i + nums[i]. Define max_reach as the maximum of f(j) for all j in [0, current_index]. If max_reach >= n-1 (where n is the array length), return true.

Constraint Analysis

1. 1 <= nums.length <= 1e4:
   • Prohibits O(n²) brute-force approaches (e.g., checking all paths).
   • Edge case: Single-element arrays (nums = [0]) trivially return true.
2. 0 <= nums[i] <= 1e5:
   • Zero values can create “traps” (e.g., [3,2,1,0,4]).
   • Large jump values require efficient tracking (e.g., nums[i] = 1e5).

2. Intuition Scaffolding

Analogies

1. Real-World: Crossing a river using stones where each stone shows how many steps ahead you can leap.
2. Gaming: A platformer game where each power-up determines your next jump distance.
3. Math: Maximizing a cumulative function under incremental constraints.

Common Pitfalls

1. Greedy Miscalculations: Choosing the largest jump at every step may skip critical indices.
2. Early Termination: Returning false prematurely if nums[i] = 0 without checking prior jumps.
3. Index Confusion: Off-by-one errors when comparing to n-1.
4. Overlooking Zero-Length Arrays: Handling n=1 requires explicit validation.
5. Redundant Checks: Recomputing reachability for indices already known to be inaccessible.

3. Approach Encyclopedia

Greedy Algorithm

• Idea: Track the farthest reachable index. If it surpasses the last index, succeed.
• Pseudocode:

  Initialize max_reach = 0  
  For i from 0 to n-1:  
      if i > max_reach: return false  
      max_reach = max(max_reach, i + nums[i])  
      if max_reach >= n-1: return true  
  return true  
  

• Complexity Proof:
  • Time: O(n) – Single pass through the array.
  • Space: O(1) – Only variables max_reach and loop index.
• Visualization:

  Indices: 0  1  2  3  4  
  nums:   [2, 3, 1, 1, 4]  
  max_reach evolves as:  
  0 → 2 (0+2) → 4 (1+3) → ... → success at i=1  
  

4. Code Deep Dive

Optimal Solution Code:

def canJump(nums):  
    max_reach = 0  
    for i in range(len(nums)):  
        if i > max_reach:  
            return False  
        max_reach = max(max_reach, i + nums[i])  
        if max_reach >= len(nums) - 1:  
            return True  
    return True  

Line-by-Line Explanation:

• Line 2: Initialize max_reach to track the farthest accessible index.
• Line 3: Iterate through each index i.
• Line 4-5: If current index is unreachable, terminate early.
• Line 6: Update max_reach to include the farthest point reachable from i.
• Line 7-8: Early exit if the last index is reachable.

Edge Case Handling:

• Example 2 (nums = [3,2,1,0,4]):
  • At i=3, max_reach = 3 (from prior indices). i + nums[i] = 3 + 0 = 3 → max_reach remains 3.
  • Next iteration (i=4): i=4 > max_reach=3 → return false.

5. Complexity War Room

Hardware Considerations:

• For n=1e4, the loop runs in ~10µs on modern CPUs (assuming 1 cycle per iteration).
• Memory usage is negligible (two integers).

Approach Comparison:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n²)	O(1)	6/10	❌ (Timeouts)
Greedy	O(n)	O(1)	9/10	✅ Optimal

6. Pro Mode Extras

Variants:

• Minimum Jumps: Find the least number of jumps to reach the end (LeetCode 45).
• Two-Directional Jumps: Allow jumping left or right (requires BFS).

Interview Cheat Sheet:

• First Mention: “This is solvable greedily in O(n) time by tracking reachability.”
• Key Insight: “If you can reach index i, you can also reach all indices before it.”