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.
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 <= 1040 <= nums[i] <= 105The Jump Game asks whether you can reach the last index of an array where each element represents the maximum jump length from that position. A common way to reason about the problem is to track how far you can move forward from each index.
A Dynamic Programming perspective considers whether each index is reachable based on previous positions that can jump to it. While this approach helps build intuition, it may require checking multiple earlier positions, leading to higher time complexity.
The more efficient strategy uses a Greedy approach. As you iterate through the array, maintain the farthest index you can currently reach. If the current index ever exceeds this reachable boundary, progressing further becomes impossible. Otherwise, continuously update the farthest reachable position.
This greedy insight allows the problem to be solved in a single pass with minimal extra memory, making it the preferred interview solution.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy (Farthest Reach) | O(n) | O(1) |
| Dynamic Programming | O(n^2) | O(n) |
NeetCode
This approach involves maintaining a variable maxReach that stores the farthest index we can reach. We iterate through each index of the array and update maxReach. If at any index i, i is greater than maxReach, it means we cannot proceed further and thus return false. If we can iterate through the array successfully, return true.
Time Complexity: O(n), where n is the number of elements in the array. We make a single pass through the array.
Space Complexity: O(1), as we use only constant extra space.
1#include <stdbool.h>
2
3bool canJump(int* nums, int numsSize) {
4 int maxReach = 0;
5 for (intIn this C solution, we iterate over the array and update the maxReach variable, which tracks the furthest index we can reach. If at any point the current index is greater than maxReach, we return false because it means we are stuck. If we are able to iterate through the entire array, it means we can reach the last index, so we return true.
This approach uses a Dynamic Programming (DP) table to track whether you can reach each index. Initialize a boolean array dp of the same length as nums, set all elements to false except the first (set to true since you're already at the start). Iterate through the array, and for each index marked true, update reachable indices as true using the jump capability at that index. Finally, return the boolean value of the last index.
Time Complexity: O(n^2), due to potential nested loop invocations over n indices.
Space Complexity: O(n), for the DP array storing reachable status for elements.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Jump Game is a well-known interview question frequently asked in companies like Google, Amazon, and Meta. It tests a candidate's ability to recognize greedy patterns and optimize from a naive dynamic programming idea.
The problem primarily relies on array traversal and index tracking rather than specialized data structures. Most optimal solutions only maintain a few variables to track the maximum reachable index.
The optimal approach is a greedy strategy that tracks the farthest index reachable while scanning the array. If the current index ever exceeds the farthest reachable position, reaching the end is impossible. This method solves the problem in O(n) time with constant space.
Jump Game can be approached using both dynamic programming and greedy techniques. While DP helps illustrate reachability from earlier indices, the greedy method is more efficient and is typically expected in coding interviews.
Here in C, we initialized a DP array with dp[0] set to true. For each true index i, the loop assesses how many indices beyond i are accessible and marks them as true, using the allowed jump.
At the end, we determine the reachability of the last index based on dp[numsSize-1].