Minimum Forward Jumps
Medium About 25 min Free, no account needed
Cross a jump array with the fewest hops, including dead ends, without enumerating every reachable edge.
The brief
Start at index 0. From index i, you may land at any later index up to i + reach[i], inclusive. Return the fewest jumps needed to land at the last index, or -1 if it is unreachable.
Solve([2, 3, 1, 1, 4]) returns 2: jump from 0 to 1, then to 4. Choosing the farthest immediate landing is not always optimal.
Empty and single-element arrays return 0. There are at most 200,000 nonnegative 32-bit values. A jump may have a reach beyond the array; only valid landing indices matter. Do not mutate the input. Enumerating every possible jump is too slow for the large case.
Starter code
using System;
public class Solution
{
public int Solve(int[] reach)
{
// TODO: implement the contract without changing the input.
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Breadth-first search
- Explore a graph or grid level by level for shortest unweighted distances and spreading processes.
- Greedy algorithms
- Make the locally best choice when an exchange argument proves it stays globally optimal.
Related katas
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Container With Most Water Medium Free Pick two lines that, with the x-axis, hold the most water.
- Integer to Roman Medium Free Write Roman numerals the way Romans did - greedily.
- Number of Islands Medium Free Count the connected patches of land in a grid.