Introduction

Jump Game is one of the most popular Greedy problems.

You are given:

  • An array nums
  • nums[i] represents the maximum jump length from index i

Goal:

Determine whether you can reach the last index.

Example

Input

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

Output

true

Explanation

Start at index 0Jump to index 1
Jump to index 4
Reached the end.

Key Observation

Track the farthest position reachable so far.

If the current index becomes greater than the farthest reachable position, reaching the end is impossible.

Algorithm

  1. Initialize farthest = 0.
  2. Traverse the array.
  3. If current index > farthest:
    • Return false.
  4. Update farthest reachable position.
  5. If farthest reaches last index:
    • Return true.
  6. Continue traversal.

Dry Run

Input

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

Index 0

farthest = max(0, 0+2)farthest = 2

Index 1

farthest = max(2, 1+3)farthest = 4

Index 2

 Last index reached

Index 4

 Last index reached

Answer

true

Approach : Greedy

Always keep track of the maximum index reachable at any point.

If we can continuously extend our reachable range to include the last index, the answer is true.

Practice

Complexity Analysis

Time Complexity: O(n)Explanation: The array is traversed exactly once while maintaining the farthest reachable position.

Space Complexity: O(1)
Explanation: Only one variable is used to track the farthest reachable index.

Why This Problem is Important

Jump Game is a classic greedy optimization problem that teaches how local reachability information can determine a global answer.

Common Beginner Mistakes

  • Trying all possible jumps using recursion.
  • Using DP unnecessarily.
  • Not checking unreachable indices.
  • Confusing Jump Game with Jump Game II.

Interview Tip

Always mention:

The key idea is tracking the farthest reachable position. If the current index is beyond that position, reaching the end is impossible.

Related Questions

  • Jump Game II
  • Gas Station
  • Best Time to Buy and Sell Stock II
  • Can Place Flowers
  • Partition Labels

Final Takeaway

Jump Game is a classic greedy problem where we continuously track the farthest reachable index. If we never get stuck before reaching the last index, the answer is true. This simple observation leads to an optimal O(n) solution.

Why This Problem is Important

Jump Game is a classic greedy optimization problem that teaches how local reachability information can determine a global answer.

Common Beginner Mistakes

  • Trying all possible jumps using recursion.
  • Using DP unnecessarily.
  • Not checking unreachable indices.
  • Confusing Jump Game with Jump Game II.

Interview Tip

Always mention:

The key idea is tracking the farthest reachable position. If the current index is beyond that position, reaching the end is impossible.

Related Questions

  • Jump Game II
  • Gas Station
  • Best Time to Buy and Sell Stock II
  • Can Place Flowers
  • Partition Labels

Final Takeaway

Jump Game is a classic greedy problem where we continuously track the farthest reachable index. If we never get stuck before reaching the last index, the answer is true. This simple observation leads to an optimal O(n) solution.