LeetCode · #55

Jump Game Solution

Given an array where each element is the max jump length from that position, determine if you can reach the last index.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #55

🏗️

Pattern

Greedy — reachability tracking

Given integer array nums where nums[i] is the max jump length from index i, return true if you can reach the last index from index 0.

Example

Input: nums = [2,3,1,1,4]
Output: true // Jump 1 step from 0→1, then 3 steps from 1→4. Input: nums = [3,2,1,0,4]
Output: false // Stuck at index 3 (value 0).

Constraints

• 1 ≤ nums.length ≤ 10⁴ • 0 ≤ nums[i] ≤ 10⁵

Section Two · Approach 1

Backtracking — O(2ⁿ)

From index 0, try every possible jump length (1 to nums[0]). Recurse from each landing index. Return true if any path reaches the end.

Why it works

Exhaustively explores all jump sequences.

Why we can do better

Problem: Exponential branching. We don't need to track paths — just whether we can reach each position. A single left-to-right pass tracking the farthest reachable index suffices.

Java — DP (bottom-up)

 class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
        dp[0] = true;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (dp[j] && j + nums[j] >= i) { dp[i] = true; break; }
return dp[n - 1];
    }
}

Python — DP (bottom-up)

 class Solution:
def canJump(self, nums: list[int]) -> bool:
        n = len(nums)
        dp = [False] * n
        dp[0] = True for i in range(1, n):
for j in range(i):
if dp[j] and j + nums[j] >= i:
                    dp[i] = True; break return dp[-1]

Metric	Value
Time	O(n²)
Space	O(n)

Section Three · Approach 2

Greedy — O(n) time, O(1) space

Track the farthest reachable index. Scan left to right: if the current index exceeds the farthest reachable, you're stuck. Otherwise, update the farthest as max(farthest, i + nums[i]).

💡 Mental model: Imagine walking along a hallway with fuel tanks on the floor. Each fuel tank tells you how many more steps you can travel. As you walk, you keep track of the farthest point your fuel can carry you. If you ever step past your fuel range, you're stranded. If your fuel range reaches or passes the exit, you escape.

Algorithm

Initialize farthest = 0.
For i from 0 to n-1: if i > farthest, return false. Else farthest = max(farthest, i + nums[i]).
Return true (loop completed without getting stuck).

🎯 When to recognize this pattern: "Can you reach the end?" with forward-only movement and variable step sizes. The signal: reachability on a 1D array. Track farthest point greedily. Also the foundation for LC 45 (Jump Game II — minimum jumps).

Why greedy is correct: If you can reach index i, you can reach every index between 0 and i + nums[i]. The farthest reachable monotonically increases (or stays). No backtracking needed — reaching farther is always at least as good.

Section Four · Trace

Visual Walkthrough

Trace for nums = [2, 3, 1, 1, 4].

Jump Game — Greedy Reachability

Section Five · Implementation

Code — Java & Python

Java — Greedy

 class Solution {
public boolean canJump(int[] nums) {
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest) return false; // can't reach i
farthest = Math.max(farthest, i + nums[i]);
        }
return true;
    }
}

Python — Greedy

 class Solution:
def canJump(self, nums: list[int]) -> bool:
        farthest = 0 for i, n in enumerate(nums):
if i > farthest: return False
farthest = max(farthest, i + n)
return True

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DP (bottom-up)	O(n²)	O(n)	Boolean array; inner loop per index
DP backward (last good)	O(n²)	O(n)	Track last good index from right
Greedy ← optimal	O(n)	O(1)	Single variable; one pass

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single element	`[0]`	Already at end. Return true.
All zeros	`[0,0,0]`	Stuck at index 0. Return false (n>1).
Large first jump	`[10,0,0,0]`	Jump from 0 covers entire array. True.
Zero at end	`[2,3,1,0]`	Zero at last index doesn't matter — you're already there.
Stuck at zero	`[1,0,1]`	Reach index 1 (value 0), can't proceed. False.

⚠ Common Mistake: Checking nums[i] == 0 and immediately returning false. A zero at index i only matters if farthest == i (you can't get past it). If farthest > i, you bypassed the zero via an earlier longer jump.

← Back to Greedy problems

LearningTree

LC 55 · Jump Game — Solution & Explanation | DSA Guide