Hut-to-Hut Trek
You are planning a long trek along a trail with mountain huts, numbered from 0 at the trailhead to the last hut at the end. You must sleep in a hut every night. The guidebook says, for each hut, how far you can walk in one day starting from there: from hut i, a day's walk can take you to any of the next reach[i] huts. Steep sections give small numbers, easy valleys big ones.
You want to finish in as few days as possible.
Your task
Write fewestDays(reach). In one day you may go from hut i to any hut j with i < j ≤ i + reach[i]. Return the fewest days needed to get from hut 0 to hut reach.length - 1.
The last hut is always reachable. If there is only one hut, you are already there: return 0.
fewestDays(reach: int[]) → int
Examples
reach = [2, 4, 1, 1, 1, 1]
2
Day 1: hut 0 to hut 1. Day 2: hut 1 can reach up to hut 5, the last one. Walking as far as possible on day 1 (to hut 2) is a trap: from there the huts only allow one step a day, and the trek takes 4 days.
reach = [3, 1, 1, 3, 0, 2, 0]
2
Day 1: hut 0 to hut 3. Day 2: hut 3 reaches huts 4, 5 and 6, and 6 is the last. One day is not enough, because hut 0 reaches only up to hut 3.
Constraints
- 1 ≤ reach.length ≤ 10,000
- 0 ≤ reach[i] ≤ 100,000
- The last hut can always be reached from hut 0.
Start with brute force
Treat it as a shortest path: a breadth-first search from hut 0, where each hut links to every hut within its reach. That is correct, but hut i has up to reach[i] links, so the search can look at O(n²) links: about 50 million for 10,000 huts with long reaches.
Another tempting idea, "each day walk as far as you can", is fast but wrong, as the first example shows.
Hints
0 of 4 shown- Hint 1
On the first example, write down every hut you can sleep in after day 1. Then every hut you could sleep in after day 2. What shape do those sets have?
- Hint 2
After each day, the huts you could be in form a block of consecutive huts. Day 1's block is huts 1 to
reach[0]. Day 2's block ends at the farthest point reachable from any hut in day 1's block. - Hint 3
So you never need to decide which hut to stop at. Walk the huts in order, and while you are inside the current day's block, track the farthest hut that the next day could reach.
- Hint 4
Keep
days,dayEnd(end of the current block) andfar. For each hutibefore the last: updatefar = max(far, i + reach[i]). WhenireachesdayEnd, you must spend another day:days++anddayEnd = far.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Think in blocks, not routes. After d days you could be in any hut up to some dayEnd. The next day's block ends at the farthest hut reachable from anywhere in the current block. Count how many blocks it takes to cover the last hut.
Trace [2, 4, 1, 1, 1, 1]:
- i = 0:
far = 0 + 2 = 2. i equalsdayEnd = 0, so a day starts: days = 1,dayEnd = 2. Day 1 can end anywhere in huts 1 to 2. - i = 1:
far = max(2, 1 + 4) = 5. - i = 2:
far = max(5, 3) = 5. i equalsdayEnd: days = 2,dayEnd = 5. - i = 3 and 4:
farstays 5, and i never reachesdayEndagain before the loop stops at the last hut. Answer: 2.
The loop stops before the last hut. If it included the last hut and dayEnd happened to land exactly there, you would count one day too many.
function fewestDays(reach) {
let days = 0;
let dayEnd = 0; // last hut reachable within `days` days
let far = 0; // last hut reachable within `days + 1` days
for (let i = 0; i < reach.length - 1; i++) {
far = Math.max(far, i + reach[i]);
if (i === dayEnd) { // leaving today's block: one more day
days++;
dayEnd = far;
}
}
return days;
}def fewest_days(reach):
days = 0
day_end = 0 # last hut reachable within `days` days
far = 0 # last hut reachable within `days + 1` days
for i in range(len(reach) - 1):
far = max(far, i + reach[i])
if i == day_end: # leaving today's block: one more day
days += 1
day_end = far
return daysRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.