Net Climb Stretches
A cycling app splits every ride into kilometres and records the net change in height over each one: +40 for a kilometre that climbs 40 metres, -15 for one that drops 15. This month's challenge pays out a badge for every stretch of back-to-back kilometres whose net climb is exactly the height of a famous tower.
Stretches can overlap, and any stretch of one or more kilometres counts. The app needs to know how many badges your ride earned.
Your task
Write countStretches(changes, k). Return how many pairs of indexes i ≤ j there are such that changes[i] + changes[i + 1] + ... + changes[j] === k.
Changes and k can be negative or zero. An empty ride has no stretches, so it returns 0.
countStretches(changes: int[], k: int) → int
Examples
changes = [2, 3, -1, 1, 4] k = 5
3
Three stretches add up to 5: kilometres 0 to 1 (2 + 3), kilometres 0 to 3 (2 + 3 - 1 + 1) and kilometres 3 to 4 (1 + 4). The first two overlap, and both count.
changes = [4, -4, 4] k = 0
2
A climb and a matching drop cancel out. Kilometres 0 to 1 and kilometres 1 to 2 both have a net change of 0, so the answer is 2.
Constraints
- 0 ≤ changes.length ≤ 20,000
- -1,000 ≤ changes[i] ≤ 1,000
- -10,000,000 ≤ k ≤ 10,000,000
Start with brute force
Try every start i, and from it extend the end j one kilometre at a time, keeping a running total. Count every time the total equals k.
That is n(n + 1)/2 stretches, about 200 million for a 20,000 km log. A sliding window does not rescue it: with descents the total can go down as the window grows, so you can never tell whether to grow or shrink it.
Hints
0 of 4 shown- Hint 1
Write down the running height after each kilometre of
[2, 3, -1, 1, 4], starting from 0 before the ride. How can you read the net climb of kilometres 3 to 4 off that list? - Hint 2
The running heights are 0, 2, 5, 4, 5, 9. The net climb from kilometre
itojis (height afterj) minus (height beforei). For kilometres 3 to 4 that is 9 - 4 = 5. - Hint 3
So a stretch ending at the current kilometre is worth
kexactly when some earlier running height equalscurrent - k. How many stretches end here? As many as there are earlier running heights with that value. - Hint 4
Walk once, keeping the running height and a map from height → how many times it has occurred so far, starting with
{0: 1}for the start of the ride. At each kilometre, add the change, addcount[height - k]to the answer, then record the new height in the map.
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
Track your running height from the start of the ride (a prefix sum). The net climb of any stretch is the height at its end minus the height just before its start. So instead of asking "which stretches sum to k?", ask at each kilometre: "how many earlier running heights were exactly k below where I am now?" A map of height → count answers that in one step.
Trace [2, 3, -1, 1, 4] with k = 5. Start with seen = {0: 1}: before the ride, your height is 0.
- +2 → height 2. Need 2 - 5 = -3: not seen. Record 2. badges = 0.
- +3 → height 5. Need 0: seen once (the start). That is kilometres 0 to 1. badges = 1. Record 5.
- -1 → height 4. Need -1: not seen. Record 4.
- +1 → height 5. Need 0: seen once. That is kilometres 0 to 3. badges = 2. Now 5 has been reached twice.
- +4 → height 9. Need 4: seen once (after kilometre 2). That is kilometres 3 to 4. badges = 3.
Three details carry the whole solution. Seed the map with {0: 1}, or stretches that start at kilometre 0 are missed. Store counts, not just "seen", because the same height can be reached several times and each one starts a different stretch. And look up before you record the current height, or with k = 0 you would count an empty stretch.
function countStretches(changes, k) {
const seen = new Map([[0, 1]]); // running height -> times reached
let height = 0, badges = 0;
for (const c of changes) {
height += c;
// every earlier height of (height - k) starts a stretch worth k
badges += seen.get(height - k) || 0;
seen.set(height, (seen.get(height) || 0) + 1);
}
return badges;
}def count_stretches(changes, k):
seen = {0: 1} # running height -> times reached
height = badges = 0
for c in changes:
height += c
# every earlier height of (height - k) starts a stretch worth k
badges += seen.get(height - k, 0)
seen[height] = seen.get(height, 0) + 1
return badgesRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.