Counting steps without a queue

Breadth-first search over an array, where each level is a contiguous stretch and needs no queue at all.

Why it works

Why each level is contiguous

Positions reachable in one step form a stretch starting at the beginning. Anything reachable in two steps is reachable from somewhere in that stretch, and since jumps can be any length up to their maximum, every position between is also reachable.

So a level is fully described by two numbers: where it ends and where the next one ends. No queue, no visited set, two variables.

Below, the levels are worked out by hand for one input, so that the two numbers can be seen before any loop is written.

1jumps = [2, 3, 1, 1, 4]2 3reachable = {0}4level = 05while 4 not in reachable:6    level += 17    nxt = set()8    for position in reachable:9        for step in range(1, jumps[position] + 1):10            nxt.add(position + step)11    reachable = nxt12    print(f"after {level} jump(s):", sorted(reachable))

Each level is a contiguous stretch, which is why two numbers describe it and a queue is unnecessary.

Quick check· 5 min

Where should the walk stop?

The walk spends a jump each time it reaches the end of the current level. On an input of n positions, which range should it walk, and why?

Positions 0 through n - 2, because standing on the final position means you have already arrived and owe nothing furtherPositions 0 through n - 1, because every position has to contribute its reach to the running maximumPositions 1 through n - 1, because no jump is spent to stand on the starting positionEither; the final position can never be a level boundary, so it makes no difference

Problem· 25 min

Jump Game Ii

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 = [2, 3, 1, 1, 4]2 3reachable = {0}4level = 05while 4 not in reachable:6 level += 17 nxt = set()8 for position in reachable:9 for step in range(1, jumps[position] + 1):10 nxt.add(position + step)11 reachable = nxt12 print(f"after {level} jump(s):", sorted(reachable))