Find the Highest Altitude
Find the Highest Altitude: given the net gain between consecutive points, starting from altitude 0, return the highest altitude reached.
- 1 <= gain.length <= 100
- -100 <= gain[i] <= 100
Intuition
Find the highest altitude takes an array of net elevation gains and returns the highest point reached. The biker starts at altitude 0, and the input holds the change between consecutive points, not the altitudes themselves.
That distinction is the whole problem. The array is a list of deltas, so the actual altitude at any point is the running sum of everything before it:
- Accumulate a running total as you scan, and track the maximum value it reaches — that is a prefix sum with a maximum, nothing more.
A frequent misreading is to return max(gain), the largest single climb. That is a different quantity entirely: a sequence of small positive gains can reach a higher altitude than one large gain followed by descents.
The starting altitude of 0 must be included as a candidate. If every gain is negative, the biker only ever descends, and the highest point is the starting point:
Initialising the maximum to 0 rather than to negative infinity handles this without a branch.
The running total itself starts at 0 as well, and each element is added before the maximum is updated — the altitude after a gain is what matters, not before it.
No array of altitudes needs to be built. A single accumulator and a single maximum are enough, so the space stays constant regardless of input size.
The tell is 'net change' or 'difference between consecutive' — the values are deltas, and the quantity you actually want is their prefix sum. Once you spot that, this is the same machinery as Running Sum of 1D Array with a maximum tracked alongside.
Approach
Before reading on: the array gives changes, not heights. Work out what the altitude is after three legs, and decide whether the starting point can ever be the answer. Aim for O(n) with O(1) space.
Read the input as deltas
The array holds changes in altitude, not altitudes. The actual height at any point is the running sum of every gain before it.
Reject the single-gain reading
Returning max(gain) answers a different question. Several small climbs can reach a greater altitude than one large climb followed by descents.
Accumulate a running total
Add each gain to a running sum as you scan. That sum is the current altitude at every step, with no array needed.
Track the maximum after each step
Update the maximum after adding the gain, since the altitude reached is what counts. Updating before would lag one element behind.
Include the starting point
Initialise the maximum to 0, not negative infinity. If every gain is negative the highest point is the start, and this handles it without a branch.
Cost of the scan
One pass with two variables gives O(n) time and O(1) space — no prefix array is required.
Solution & live demo
Common pitfalls
Returning the maximum of the input
return max(gain)
altitude += step highest = max(highest, altitude)
gain holds changes, not altitudes. On [-5,1,5,0,-7] this returns 5, but the highest altitude actually reached is 1.
Not counting the starting altitude
highest = gain[0]
highest = 0
The journey begins at 0, which is a valid altitude. On an all-downhill route like [-4,-3,-2] the correct answer is 0, but seeding from the first gain reports -4.
Returning the final altitude
for step in gain:
altitude += step
return altitudehighest = max(highest, altitude) # inside the loop
The end of the ride is not necessarily its highest point. The maximum must be captured as the walk proceeds, since a mid-journey peak is lost once the descent begins.
Edge cases
Every altitude is below 0, so the answer is the starting altitude, 0.
The altitude rises monotonically and the answer is the final total.
The maximum is reached mid-journey, so comparing at every step is essential.
One addition gives 10, which beats the starting 0.
The peak of 3 is recorded before the descent returns to 0.