Shortest Steep Climb
A cycling coach plans hill training on a long mountain road. The road is split into segments of equal length, and the map lists how many metres each segment climbs, in order. The road only goes up, so every number is positive.
For today's drill, a rider must climb at least target metres without stopping, over as few segments as possible. The coach wants the shortest unbroken stretch of road that climbs that much.
Your task
Write shortestClimb(gains, target). Return the smallest number of consecutive segments whose gains add up to at least target.
If no stretch climbs enough, not even the whole road, return 0.
shortestClimb(gains: int[], target: int) → int
Examples
gains = [30, 10, 60, 20, 40, 50] target = 100
3
Segments 4 and 5 climb 40 + 50 = 90, just short. The three segments 3 to 5 climb 20 + 40 + 50 = 110, and segments 0 to 2 climb exactly 100, which counts. No two neighbouring segments reach 100 (the largest pair is 90), so the answer is 3.
gains = [5, 5, 5] target = 20
0
The whole road only climbs 15 metres. No stretch reaches 20, so return 0.
Constraints
- 0 ≤ gains.length ≤ 10,000
- 1 ≤ gains[i] ≤ 10,000
- 1 ≤ target ≤ 1,000,000,000
Start with brute force
For every starting segment, add segments one by one until the total reaches target, and record how many it took. Keep the smallest count.
That is up to n steps for each of n starts. With 10,000 segments and a large target it is about 50 million additions, and each start re-adds almost the same segments as the start before it.
Hints
0 of 4 shown- Hint 1
In the first example, start at segment 0 and keep adding segments until you reach 100. You stop at segment 2. Now, if you also drop segment 0, do you still have enough?
- Hint 2
Once a stretch is long enough, the only way to find a shorter one with the same right end is to remove segments from the left. Because every gain is positive, removing one always lowers the total.
- Hint 3
So use a window: grow it on the right until it climbs enough, then shrink it from the left for as long as it still climbs enough, recording the length each time.
- Hint 4
Keep
leftand a runningtotal. For eachright: addgains[right]. Then, whiletotal ≥ target, recordright - left + 1if it is smaller than the best, subtractgains[left]and moveleftforward.
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
Because every gain is positive, adding a segment always raises the total and removing one always lowers it. That makes a sliding window safe: grow the right edge until the stretch is steep enough, then pull in the left edge as far as you can while it stays steep enough.
Trace [30, 10, 60, 20, 40, 50] with target 100:
- Add 30, 10, 60: total 100 at
right= 2. Enough. Length 3, best = 3. Drop 30: total 70. Not enough, stop shrinking. - Add 20: total 90. Not enough.
- Add 40: total 130, window is segments 1 to 4. Length 4, not better. Drop 10: total 120, length 3 (segments 2 to 4), not better. Drop 60: total 60. Stop.
- Add 50: total 110, segments 3 to 5. Length 3, not better. Drop 20: total 90. Stop.
The answer is 3. Each segment entered the window once and left at most once, so the whole thing is about 2n steps. Note the window idea depends on the gains being positive: with negative numbers, dropping a segment could raise the total and the shrinking rule would be wrong.
function shortestClimb(gains, target) {
let left = 0, total = 0, best = 0;
for (let right = 0; right < gains.length; right++) {
total += gains[right];
// Shrink from the left while the stretch still climbs enough.
while (total >= target) {
const len = right - left + 1;
if (best === 0 || len < best) best = len;
total -= gains[left];
left++;
}
}
return best;
}def shortest_climb(gains, target):
left = total = best = 0
for right, g in enumerate(gains):
total += g
# Shrink from the left while the stretch still climbs enough.
while total >= target:
length = right - left + 1
if best == 0 or length < best:
best = length
total -= gains[left]
left += 1
return bestRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.