Jump Game Greedy DSA Solution

Learning Outcome

After this lesson, you should be able to turn many possible jump paths into one farthest-reach invariant.

Problem Statement

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

Input	Output	Why
`nums = [2,3,1,1,4]`	`true`	Index 0 can reach index 1, and index 1 can reach the end.

Brute Force Approach

Try every possible jump path recursively. This repeats states and can become exponential.

Optimized Approach

Scan left to right and maintain the farthest reachable index. If the current index is beyond farthest, the end is impossible.

Exact Pseudocode

farthest = 0
for i from 0 to n - 1:
  if i > farthest:
    return false
  farthest = max(farthest, i + nums[i])
return true

Reference Code

class Solution:
    def canJump(self, nums):
        farthest = 0
        for i, jump in enumerate(nums):
            if i > farthest:
                return False
            farthest = max(farthest, i + jump)
        return True

Sample Dry Run

Step	State	Result
i = 0	farthest = max(0, 0 + 2)	farthest = 2
i = 1	1 is reachable, update with 1 + 3	farthest = 4
i = 2,3,4	All are within farthest	End is reachable
Return	No unreachable index found	true

Complexity

Measure	Value	Reason
Time	O(n)	Each index is checked once.
Space	O(1)	Only the farthest reachable index is stored.

Edge Cases

A single-element array is already reachable.
If i becomes greater than farthest, return false immediately.
Zeros are fine unless they block all future progress.

Interview Checklist

Check reachability before using nums[i].
Update farthest with i + nums[i].
Do not explore every path once the invariant is known.

FAQs

Why is farthest enough?

If an index is reachable, only the best future reach matters; the exact path no longer matters.

When do we fail?

We fail when the scan reaches an index greater than the farthest reachable index.

What is the core pattern?

Farthest-reach greedy.

Jump Game: Farthest Reach Greedy Pattern