How do you solve Jump Game?

Use a single pass from the end of the array to the beginning. Initialize goal as the last index. For each index i from right to left, check if i + nums[i] >= goal. If yes, update goal to i. After the loop, return true if goal is 0, false otherwise. This approach runs in O(n) time and O(1) space.

What pattern does Jump Game use?

The Pattern: Greedy Algorithms (Backward Reachability) The Heuristic: When a problem asks if a target is reachable via jumps or steps, consider working backward from the target, greedily updating the earliest reachable position to efficiently collapse the search space.

Jump Game — Greedy Algorithms

Q: What is the time complexity of Jump Game?

O(n). The algorithm iterates through the array once from right to left, performing constant-time checks and updates per element.

Problem

Given an array of non-negative integers nums, return true if you can reach the last index starting from the first index, where each element represents the maximum jump length at that position.

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

Example

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

Output: true

Starting at index 0 with jump length 2, you can jump to index 1 or 2. From index 1 with jump length 3, you can jump directly to the last index 4. The algorithm works backward from the last index, updating the 'goal' to the earliest index that can reach it. Initially, the goal is index 4. At index 3, jump length 1 allows reaching index 4, so the goal updates to 3. At index 1, jump length 3 allows reaching index 3, so the goal updates to 1. Finally, since the goal is 1 and index 0 can jump to index 1, the goal updates to 0, confirming the last index is reachable from the start.

Approach

Straightforward Solution

A brute-force approach tries all possible jumps from each index, exploring all paths recursively or via BFS/DFS. This leads to exponential or O(n^2) time complexity, which is inefficient for large inputs.

Core Observation

The fundamental truth is that to reach the last index, there must exist a chain of indices where each index can jump to the next, eventually reaching the end. This can be reframed as a backward reachability problem: if an index can reach the 'goal', then that index becomes the new goal.

Path to Optimal

Preview

The key insight is to work backward from the last index, maintaining a 'goal' index that represents the earliest position from which the end is reachable. Iterating from right to left, if the current index can jump to or beyond the goal, update the goal to the current index…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a single pass from the end of the array to the beginning. Initialize goal as the last index…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm iterates through the array once from right to left, performing constant-time checks and updates per element.

Space

O(1)

Only a few variables are used to track the goal index and loop counters, with no additional data structures proportional to input size.

Solution

Python

1class Solution:
  def canJump(self, nums: list[int]) -> bool:
      goal = len(nums) - 1
4
      for i in range(len(nums) - 1, -1, -1):
          if i + nums[i] >= goal:
              goal = i
      
      return goal == 0

Step-by-Step Solution

1

Initialize Goal as Last Index to Represent Target Reachability

3	`goal = len(nums) - 1`

Objective

To set the initial target position as the last index, which the algorithm will attempt to reach from earlier indices.

Key Insight

By defining the goal as the last index, the algorithm frames the problem as a backward search: each index tries to see if it can reach the current goal. This transforms the forward jump problem into a backward reachability problem, simplifying the logic and enabling a greedy solution.

Interview Quick-Check

Core Logic

Setting the goal as the last index establishes the target that all earlier indices attempt to reach.

State & Boundaries

The goal variable is updated only when an index can reach or surpass it, ensuring it always points to the earliest reachable position.

2

Iterate Backward to Update Goal Based on Reachability

To scan the array from right to left, updating the goal whenever an index can jump to or beyond it.

3

Return True if Start Index Can Reach the Goal

To determine if the first index can reach the last index by checking if the goal has moved to 0.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 6 Critical

if i + nums[i] >= goal:

Check if the current index can reach or surpass the current goal.

This condition identifies indices that can jump directly to the goal, allowing the goal to move leftward and shrink the target window.

Line 7 Critical

goal = i

Update the goal to the current index if it can reach the previous goal.

Updating the goal to the current index contracts the problem space, representing the earliest reachable position from which the end can be reached, which is the core greedy step.

Full line-by-line criticality + rationale for all 5 lines available on Pro.

Test Your Understanding

Why does updating the goal index backward guarantee that if the goal reaches 0, the last index is reachable from the start?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Jump Game from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Jump Game drill

or drill a free problem

1	`class Solution:`
2	`def canJump(self, nums: list[int]) -> bool:`
3	`goal = len(nums) - 1`
4
5	`for i in range(len(nums) - 1, -1, -1):`
6	`if i + nums[i] >= goal:`
7	`goal = i`
8
9	`return goal == 0`