InternDoor

Fewest jumps to the end

Mediumgreedy · arrays · breadth-first search

Reported in interviews at (where)

You stand on position 0 of a row of stones. jumps[i] is the longest jump you can make from stone i: from there you can land on any stone from i + 1 to i + jumps[i].

The last stone can always be reached. Return the fewest jumps that take you there (0 if you are already on it).

Example 1
Input
jumps = [2,4,1,1,1,3]
Output
2

Jump to stone 1, then its 4 takes you to stone 5, the last.

Example 2
Input
jumps = [0]
Output
0

You start on the last stone.

Example 3
Input
jumps = [1,1,1,1]
Output
3

One stone at a time.

Limits

  • 1 <= jumps.length <= 100000
  • 0 <= jumps[i] <= 1000
  • The last stone is always reachable.

Hints

Hint 1

Think in rounds: every stone reachable with j jumps tells you how far j + 1 jumps can go.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.