55. Jump Game
Model: qwen3.5:9b
Topics: Array,Greedy
FAANG asked: 1
Acceptance rate: 35.2%
Problem Breakdown
We are given an array nums where each element represents the maximum jump length from that specific index. We start at index 0 and need to determine if we can reach the last index of the array.
Inputs: A list of non-negative integers (nums).
Outputs: Boolean value indicating reachability.
Constraints & Edge Cases:
- Array size is between 1 and . This rules out empty arrays but requires an efficient solution (better than quadratic).
- Values are non-negative (), so we don’t need to handle negative jump lengths.
- If the array has only one element, we start at index 0 which is also the last index; this should return
True.
Intuition
A naive approach would be Depth-First Search (DFS) or Breadth-First Search (BFS), trying every possible path from the current position to see if any lead to the end. However, since we can jump multiple steps at once, branching factor is high ( in worst case). This will time out on large inputs.
The key insight for a greedy solution: We don’t need to track specific paths or combinations of jumps. Instead, we only care about the furthest index reachable so far (max_reach).
As we iterate through the array from left to right:
- If our current position
iis beyond what we can reach (i > max_reach), it means there’s a gap in jumps that blocks us, and we cannot proceed further. We returnFalse. - Otherwise, we update
max_reachby considering the jump from indexi:max(max_reach, i + nums[i]).
If we complete the loop without getting blocked, it implies every step was reachable, so we can reach the end (or have already passed it).
Approach
- Initialize a variable
farthestto track the maximum index reachable from any point visited so far. Start at 0. - Iterate through each index
iin the array up to the second-to-last element. We stop before the last one because if we can reach it, success is guaranteed; no need to jump from the last index. - Inside the loop:
- Check if current index
i > farthest. If true, returnFalseimmediately (we are stuck). - Update
farthest = max(farthest, i + nums[i]).
- Check if current index
- After iterating through all reachable indices without getting blocked, return
True.
Complexity Analysis
- Time: where N is the length of
nums. We perform a single pass over the array with constant-time operations inside the loop. - Space: . We only use two variables (
farthestand index counter), regardless of input size.
Solution
def canJump(nums):
"""
Determines if it's possible to reach the last index from index 0.
Args:
nums (List[int]): Array where each element is max jump length at that position.
Returns:
bool: True if last index is reachable, False otherwise.
"""
farthest = 0
# Iterate up to the second-to-last index because we don't need
# to calculate a jump from the final destination itself.
for i in range(len(nums) - 1):
# If current position exceeds our furthest reachable point,
# it's impossible to proceed further.
if farthest < i:
return False
# Update the maximum index we can reach with a jump from here
farthest = max(farthest, i + nums[i])
return True
Edge Cases Handled
- Single Element Array: The loop
range(len(nums) - 1)becomes empty (e.g., length 1). Function skips the loop and returnsTrue, which is correct since we are already at the end. - Blocked Path Early On: If a zero appears early that prevents reaching subsequent indices,
farthestwill not increase enough to cover future indices, causingi > farthestcheck to trigger correctly on the next iteration or immediately if stuck right away. - Large Jump Values: The logic handles large jump lengths naturally by updating
farthest. Since Python integers handle arbitrary size (and constraints are within standard integer limits), overflow is not a concern here compared to languages like C++/Java, though we still check reachability bounds rather than just summing values.