MediumGreedy Techniques

Jump Game

Explanation & Solution

Description

Given an integer array nums, where each element represents your maximum jump length at that position, determine if you can reach the last index starting from the first index.

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.

Constraints

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

Approach

Greedy Techniques pattern

1. Initialize Farthest Reachable Index

Create a variable farthest set to 0 representing the farthest index we can currently reach
We start at index 0, so initially we can only reach index 0

2. Iterate Through the Array

Loop through each index i from 0 to nums.length - 1
At each step, check whether the current index i is reachable (i.e., i <= farthest)

3. Check If Current Index Is Unreachable

If i > farthest, it means we cannot reach index i from any previous position
In this case, return false immediately since the last index is also unreachable

4. Update Farthest Reachable Index

At index i, we can jump up to nums[i] steps, reaching index i + nums[i]
Update farthest = Math.max(farthest, i + nums[i]) to track the maximum reachable position

5. Early Termination on Success

If farthest >= nums.length - 1, we can already reach the last index
Return true immediately without processing the remaining elements

6. Return Result

If the loop completes without returning false, the last index is reachable, so return true

Key Insight

The greedy approach works because we only need to know the farthest position reachable so far, not the specific path taken
If we can reach index i, we can reach every index between 0 and i, so tracking the maximum is sufficient
The overall complexity is O(n) time with O(1) space, making this the optimal solution

Visualization

Input:

[2, 3, 1, 1, 4]

—

Press ▶ or use ← → to step through

Pointer iPointer jProcessedDone

4 steps

Solution Code

Jump Game II