Reachability as one running number

You do not need to know how you got somewhere. Only how far anything can now take you.

Why it works

Carry the furthest reachable position

Walk forward keeping one number: the furthest position anything seen so far can reach. At each position, if that number has not reached where you are standing, nothing can, and the answer is no.

Otherwise extend it with what this position offers. The key observation is that how you reached a position is irrelevant. If it is reachable at all, everything it can reach is reachable.

That is what collapses the table. Reachability is not a property of routes, it is a property of positions, and one running maximum captures all of it.

Watch that single number on an input where the walk does get stranded.

1jumps = [3, 2, 1, 0, 4]2 3furthest = 04for position, jump in enumerate(jumps):5    reached = position <= furthest6    print(f"at {position}: furthest so far {furthest}, standing here is"7          f" {'fine' if reached else 'impossible'}")8    if not reached:9        break10    furthest = max(furthest, position + jump)

The zero at position 3 adds nothing, so the reach stalls and position 4 is never available.

Predict the output· 5 min

Predict the output: extending before checking

This updates the running reach before checking whether the current position was reachable. The first input is not finishable and the second is. Type the two values it prints.

Python

1def can_finish_broken(jumps):2    furthest = 03    for position, jump in enumerate(jumps):4        furthest = max(furthest, position + jump)5        if position > furthest:6            return False7    return True8 9print(can_finish_broken([3, 2, 1, 0, 4]), can_finish_broken([2, 3, 1, 1, 4]))

Printed output

Problem· 22 min

Jump Game

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1jumps = [3, 2, 1, 0, 4]2 3furthest = 04for position, jump in enumerate(jumps):5 reached = position <= furthest6 print(f"at {position}: furthest so far {furthest}, standing here is"7 f" {'fine' if reached else 'impossible'}")8 if not reached:9 break10 furthest = max(furthest, position + jump)

1def can_finish_broken(jumps):2 furthest = 03 for position, jump in enumerate(jumps):4 furthest = max(furthest, position + jump)5 if position > furthest:6 return False7 return True8 9print(can_finish_broken([3, 2, 1, 0, 4]), can_finish_broken([2, 3, 1, 1, 4]))