Jump Game

Medium

greedy

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.

Greedy Insight: Track the farthest position you can reach. At each position, update the maximum reachable index. If at any point your current position exceeds the maximum reachable, you're stuck.

Why Greedy Works: We don't need to track all possible paths. We only care about the farthest we can reach from positions we can actually visit. If we can visit position i and nums[i] allows jumping further than our current max, we update our reach.

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.

Constraints

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

Show Hints (4)

Hint 1: At each position, what is the farthest index you can reach?

Hint 2: If the current position is beyond your maximum reach, you cannot proceed.

Hint 3: The greedy choice: always track the maximum reachable index as you iterate.

Hint 4: You succeed if maxReach >= n-1 at any point.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?