TIC
The Interns Company

Jump Game

MediumAcceptance: 38.2%
ArrayDynamic ProgrammingGreedy

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.

Constraints:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^5

Input Format:

  • An array of integers nums

Output Format:

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

Examples:

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.

Solutions

Greedy Approach

Time: O(n)
Space: O(1)

Keep track of the furthest position you can reach. If at any point, the current index is greater than the furthest position you can reach, you can't reach the end.

Backward Dynamic Programming Approach

Time: O(n²)
Space: O(n)

Start from the last index and work backwards. For each position, determine if it's possible to reach any of the previously determined 'good' positions.

Optimized Backward Approach

Time: O(n)
Space: O(1)

Start from the last index and work backwards. Keep track of the leftmost 'good' position. For each position, check if you can reach the leftmost good position.

Algorithm Walkthrough

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

Step-by-step execution:

  1. Initialize maxReach = 0
  2. i=0, nums[0]=2: maxReach = max(0, 0+2) = 2
  3. i=1, nums[1]=3: maxReach = max(2, 1+3) = 4
  4. i=2, nums[2]=1: maxReach = max(4, 2+1) = 4
  5. i=3, nums[3]=1: maxReach = max(4, 3+1) = 4
  6. maxReach >= nums.length - 1, so return true

Hints

Hint 1
If you ever reach a position where the maximum jump length is 0, can you still reach the end?
Hint 2
Think about working backwards from the last index.
Hint 3
Consider a greedy approach: track the furthest position you can reach at each step.

Video Tutorial

Jump Game - Greedy Approach

YouTube•Learn the Jump Game solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the array as a series of positions, showing the maximum jump length at each position and the furthest we can reach.

Key visualization elements:

  • current position
  • maximum reach
  • unreachable positions

Asked By

AmazonMicrosoftGoogleFacebookAppleUberAdobe

Implementation Notes

This problem is a great example of how a greedy approach can be more efficient than dynamic programming for certain problems. The key insight is to always track the furthest position you can reach.