Find the Highest Altitude
Turn a list of altitude gains into the altitudes they reach with a running sum, and keep the highest one, counting the starting point at 0.
Problem Understanding
Find the Highest Altitude (LeetCode 1732): a biker's trip has n + 1 points. It starts at point 0 with altitude 0, and gain[i] is the change in altitude from point i to point i + 1. Return the highest altitude of any point.
Examples: [-5, 1, 5, 0, -7] → 1 (the altitudes are 0, -5, -4, 1, 1, -6); [-4, -3, -2, -1, 4, 3, 2] → 0.
The Intuition: Altitudes Are Prefix Sums
Each altitude is the start plus every gain so far, so the list of altitudes is the prefix sum of gain with a 0 in front.
- Start at 0. The starting point is a real point of the trip, so the highest altitude is at least 0.
- Add each gain. The running total is the altitude at the next point.
- Keep the maximum. Compare after every step.
You never look back at an earlier altitude, so there is no need to store them. See Introduction to Prefix Sums for the full array version, and Find Pivot Index for another prefix sum kept in one variable.
Interactive Walkthrough
5 GAINS · 6 POINTS
START AT 0
gain
0
1
2
3
4
altitude
0
1
2
3
4
5
Altitude
0
Highest
0
Answer
:
The trip starts at altitude 0, which is also the highest point so far
Next
gain[0] = -5: point 1 is at 0 − 5 = -5
gain
The bottom row has one more cell than gain: applying gain[i] writes point i + 1. The highest point so far stays green. Try Example 2, where the start is the highest point.
Dry Run Table
Input: gain = [-5, 1, 5, 0, -7].
| Point | gain applied | Altitude | Highest |
|---|---|---|---|
| 0 | (start) | 0 | 0 |
| 1 | -5 | -5 | 0 |
| 2 | 1 | -4 | 0 |
| 3 | 5 | 1 | 1 |
| 4 | 0 | 1 | 1 |
| 5 | -7 | -6 | 1 |
Answer: 1.
The Solution Template
A running sum and a running maximum, both starting at 0 for the starting point.
Find the Highest Altitude Code
1var largestAltitude = function(gain) {2 let altitude = 0;3 let highest = 0;4 for (const g of gain) {5 altitude += g;6 highest = Math.max(highest, altitude);7 }8 return highest;9};
Edge Cases & Common Mistakes
- All gains negative: the start is the highest point, so the answer is 0, not the least negative altitude.
- Forgetting the start: there are n + 1 points for n gains; point 0 must be part of the maximum.
- Taking the largest gain: the question is about altitude, the running total, not the biggest single climb.
- Equal highs: a later point at the same altitude does not change the answer.
Summary
The altitudes are the prefix sums of gain with 0 in front. Keep a running altitude and the maximum, both starting at 0, and return the maximum. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet