#55

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Jump Game

Solve the Jump Game problem using state transition dynamic programming to determine if you can reach the last index of the array.

array dynamic programming greedy

Problem Statement

You are given an integer array nums. Starting from the first index, each element in the array represents the maximum jump length from that position. You need to determine if it’s possible to reach the last index of the array by using valid jumps at each step.

Return true if you can reach the last index, or false otherwise. For example, in the array [2,3,1,1,4], starting from the first index, you can jump 1 step to index 1, then 3 steps to the last index, making it possible to reach the end.

Examples

Example 1

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

Output: true

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

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 <= 104
0 <= nums[i] <= 105

Solution Approach

Greedy Approach

In the greedy approach, we iterate through the array while keeping track of the farthest index we can reach. Starting from the first index, we check if it’s possible to reach the current index. If at any point the farthest reachable index becomes less than the current index, it means we are stuck and cannot reach the last index, returning false. If we can reach or exceed the last index, we return true.

Dynamic Programming Approach

The dynamic programming approach uses a state transition where each index stores whether it’s possible to reach the last index. We iterate backward through the array, updating the reachability of each index. If an index can reach the last index or any other reachable position, we mark it as reachable. If, after processing, the first index is reachable, we return true, otherwise false.

Time Complexity Considerations

Both greedy and dynamic programming approaches operate in linear time, O(n), where n is the length of the array. The space complexity is O(1) for the greedy approach, as we only need a few variables to track the farthest reachable index. The dynamic programming approach, however, requires O(n) space to store reachability status for each index.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

For both the greedy and dynamic programming approaches, the time complexity is O(n) as each index is processed once. The greedy approach achieves constant space complexity O(1), while the dynamic programming approach requires O(n) space to store reachability states for each index.

What Interviewers Usually Probe

Do you understand the greedy approach for Jump Game and its benefits?
Can you explain how the dynamic programming solution works and its space complexity?
Will you be able to identify edge cases, such as when the array has only one element?

Common Pitfalls or Variants

Common pitfalls

Forgetting that you must update the farthest reachable index in the greedy approach.
Confusing the order of jumps in dynamic programming, which can lead to incorrect conclusions about reachability.
Misunderstanding edge cases, such as when the array has only one element or if it’s impossible to jump due to zeros in the array.

Follow-up variants

Jump Game II: Minimum Jumps
Jump Game III: Reachable Indices with Constraints
Jump Game IV: Reaching Target with Optional Restrictions

FAQ

What is the time complexity of the Jump Game problem?

The time complexity for both the greedy and dynamic programming solutions is O(n), where n is the length of the input array.

How can I solve Jump Game using dynamic programming?

The dynamic programming approach involves iterating through the array in reverse, marking reachable indices, and checking if the start index is reachable.

Can the Jump Game problem be solved using a greedy approach?

Yes, the greedy approach solves Jump Game by keeping track of the farthest index reachable from each position and ensuring no position is unreachable.

What are common edge cases for the Jump Game problem?

Common edge cases include arrays with a single element, arrays with no valid jumps (e.g., [3, 2, 1, 0, 4]), and arrays where the first element is 0.

Why does the greedy approach for Jump Game work?

The greedy approach works because it iterates over the array, always ensuring the farthest reachable index is updated. If at any point we can’t reach the next position, we know we can't reach the last index.

terminal

Solution

Solution 1: Greedy

We use a variable $mx$ to maintain the farthest index that can currently be reached, initially $mx = 0$.

1

2

3

4

5

6

7

8

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        mx = 0
        for i, x in enumerate(nums):
            if mx < i:
                return False
            mx = max(mx, i + x)
        return True

Continue Practicing

#45 jump game ii #122 best time to buy and sell stock ii #376 wiggle subsequence