Fewest Hops to Reach the Last Lily Pad
Solve this ProblemA frog stands on the first of a row of lily pads, and each pad shows the longest hop it can make forward from there. The last pad is guaranteed to be reachable. Find the fewest hops the frog needs to get from the first pad to the last.
A table of the fewest hops to every pad works, but it re-examines earlier pads again and again. Greedy windows do better: the pads reachable with k hops form a block, and the scan only needs to note how far that block can be extended by one more hop.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ hops.length ≤ 15 and 0 ≤ hops[i] ≤ 8; hops[i] is the longest hop the frog can make from pad i - ◆
The frog starts on pad 0. From pad i it may hop forward to any pad from i + 1 up to i + hops[i] - ◆
The last pad is always reachable - ◆
Return the fewest hops needed to reach the last pad (0 if there is only one pad)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Fewest Hops to Each Pad, Checking Every Earlier Pad
BruteLet fewest[p] be the fewest hops needed to land on pad p. Pad 0 needs 0. For each later pad, look at every earlier pad: if its longest hop reaches pad p, then landing on p from there costs fewest[from] + 1, so fewest[p] is the minimum of those. The answer is fewest[n − 1]. It works, but each pad is compared with every earlier pad.
O(n²)O(n)1class Solution {
2 public int fewestHops(int[] hops) {
3 int n = hops.length;
4 int[] fewest = new int[n];
5 for (int pad = 1; pad < n; pad++) {
6 fewest[pad] = Integer.MAX_VALUE;
7 for (int from = 0; from < pad; from++) {
8 if (from + hops[from] >= pad && fewest[from] != Integer.MAX_VALUE) {
9 fewest[pad] = Math.min(fewest[pad], fewest[from] + 1);
10 }
11 }
12 }
13 return fewest[n - 1];
14 }
15}Optimal — Greedy Hop Windows
OptimalThink of the pads reachable with k hops as a window that ends at currentEnd. While scanning the pads inside the current window, keep track of the farthest pad any of them can reach. When the scan gets to the end of the window, one more hop is unavoidable — take it, and the next window ends at that farthest pad. Counting how many times the scan hits the end of a window gives the fewest hops. The final pad itself is never scanned (no hop is needed from it).
O(n)O(1)1class Solution {
2 public int fewestHops(int[] hops) {
3 int n = hops.length;
4 int hopsUsed = 0, currentEnd = 0, farthest = 0;
5 for (int pad = 0; pad < n - 1; pad++) {
6 farthest = Math.max(farthest, pad + hops[pad]);
7 if (pad == currentEnd) {
8 hopsUsed++;
9 currentEnd = farthest;
10 }
11 }
12 return hopsUsed;
13 }
14}