1732. Find the Highest Altitude
Easy · solved 2026-10-01 · Open on LeetCode
prefix-sumarray
Time O(n) · Space O(1)
How to get there
Carry only what the next step needs
1. Work out the altitudes by hand. On [-5, 1, 5, 0, -7], the biker starts at 0, then reaches -5, -4, 1, 1, -6. Each altitude is the one before it plus a gain: the altitudes are running sums of gain, with point 0 in front.
2. Ask what each step needs from the past. To get the next altitude, only the current one is needed, not the whole list. To answer the question, only the highest seen so far is needed. So two numbers carry everything: the current altitude and the highest one.
3. Decide where they start. Both start at 0, because point 0 is a real point at altitude 0. When every later point is lower, as in [-4, -3, -2, -1, 4, 3, 2], the start itself is the highest point and the answer is 0.
The reusable recipe: when each value is built from the one before it and the answer is the largest of them, carry the running value and the running best through one loop; the list of values is never stored.
Let the variables' meanings write the loop
| Variable | Always means |
|---|---|
s |
the altitude of the point the loop has reached |
m |
the highest altitude among the points reached so far, including point 0 |
| Code | What happened | What it restores |
|---|---|---|
s = m = 0 |
only point 0 is reached | its altitude is 0, and it is the highest so far |
s = s+g |
the biker moves one point on | s is the new point’s altitude |
m = max(m, s) |
a new point joined the reached ones | m covers it too |
There is no branch to choose: every gain moves the biker one point, so every pass does the same two updates.
The method carries over: state what each running variable means, and each loop step is the update that keeps that meaning true for one more element.
Alternatives compared
| Approach | Time | Space | How it works |
|---|---|---|---|
| List of altitudes | O(n) | O(n) | Build every altitude into a list, then take its max. |
| Running sum (chosen) | O(n) | O(1) | Carry the current altitude and the highest so far through one loop. |
max(accumulate(gain, initial=0)) |
O(n) | O(1) | The same running sum in one line. accumulate yields each sum as max asks for it, so no list is built. |
No approach beats O(n): any gain left unread could be the one that sets the peak.
solution.py
class Solution:
def largestAltitude(self, gain: list[int]) -> int:
s = m = 0
for _, g in enumerate(gain):
s = s+g
m = max(m, s)
return mNotes
Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.