Each element of the array is the maximum number of steps you can jump forward from
that position. Starting at index 0, return true if you can reach (or pass) the last
index.
arrayStepper(nums)
Input format: space-separated non-negative integers (non-empty).
[2, 4, 2, 1, 0, 0] // → true
[2, 1, 0, 3] // → false
[0] // → true (already at the end)
At any index, the value there is the maximum steps you can jump forward — 1 up to that maximum. You can reach the end from here if any reachable next position can too. "Can I reach the end from index i" is true if i is at or past the last index, or some reachable next index j also answers true.
At or beyond the last index, you've already succeeded.
A direct implementation tries every jump distance from the current index, each leading to another index trying every distance again. Different jump sequences frequently land on the same index later. The naive recursion re-explores "can I reach the end from here" independently every time, even though the answer never depends on the path taken. Worst case, exponential redundant explorations.
Whether you can reach the end from an index depends only on that index and what's beyond it. Cache from index to true/false. Check before exploring; otherwise try each reachable next index, recurse, and return true the moment one succeeds; false if none work.
Only as many distinct indices as elements exist, each resolved once. Resolving one index tries up to n jump lengths — roughly O(n²) worst case, a solid improvement over unmemoized exponential blowup, from recognizing the recursive state collapses to a single index.
def array_stepper(nums):
memo = {}
def can_reach(i):
if i >= len(nums) - 1:
return True
if i in memo:
return memo[i]
for step in range(1, nums[i] + 1):
if can_reach(i + step):
memo[i] = True
return True
memo[i] = False
return False
return can_reach(0)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.