Find the Highest Altitude
Problem
Given an integer array gain representing the net gain in altitude between consecutive points, return the highest altitude reached after all gains are applied starting from altitude 0.
- 1 ≤ gain.length ≤ 100
- −100 ≤ gain[i] ≤ 100
Example
gain = [-5,1,5,0,-7]1Starting at altitude 0, the altitudes after each gain are: 0 + (-5) = -5, -5 + 1 = -4, -4 + 5 = 1, 1 + 0 = 1, 1 + (-7) = -6. The highest altitude reached is 1. The algorithm iterates through the gain array, updating the current altitude by adding each gain and tracking the maximum altitude seen so far. The critical moment is when the altitude reaches 1 after the third gain, which becomes the highest altitude.
Approach
Straightforward Solution
A brute-force approach would compute the altitude at each point by summing all gains up to that point repeatedly, resulting in O(n²) time complexity, which is inefficient for larger inputs.
Core Observation
The altitude at each point is the cumulative sum of all previous gains starting from zero. The problem reduces to finding the maximum prefix sum of the gain array when starting from zero.
Path to Optimal
PreviewRecognizing that altitude updates are cumulative sums suggests using a running total (prefix sum) to track altitude efficiently. By iterating once through the gain array and updating the current altitude incrementally, the algorithm achieves O(n) time complexity…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewInitialize altitude and highest altitude to zero. Iterate through the gain array, incrementally update altitude by adding each gain, and update highest altitude if the current altitude exceeds it…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm iterates through the gain array once, performing constant time operations per element.
Space
O(1)
Only a fixed number of variables are used to track the current altitude and highest altitude, regardless of input size.
Pattern Spotlight
Prefix Sum (Running Total Tracking)
When a problem involves cumulative changes over a sequence and asks for a maximum or minimum state reached, maintain a running total and track the extremum during a single pass to achieve optimal efficiency.
Solution
| 1 | class Solution: |
| 2 | def largestAltitude(self, gain: list[int]) -> int: |
| 3 | altitude = 0 |
| 4 | highest = 0 |
| 5 | |
| 6 | for change in gain: |
| 7 | altitude += change |
| 8 | highest = max(highest, altitude) |
| 9 | |
| 10 | return highest |
Step-by-Step Solution
Accumulate Altitude Changes and Update Maximum Altitude
| 3 | altitude = 0 |
| 4 | highest = 0 |
| 6 | for change in gain: |
| 7 | altitude += change |
| 8 | highest = max(highest, altitude) |
| 10 | return highest |
Objective
To iterate through each gain, update the current altitude, and track the highest altitude reached so far.
Key Insight
The altitude at each point is the sum of all previous gains plus the starting altitude zero. By maintaining a running total, the algorithm efficiently computes the altitude at each step without redundant summations. Simultaneously tracking the maximum altitude ensures the final answer is available immediately after one pass.
Interview Quick-Check
Core Logic
Maintain a running sum of altitude changes and update the maximum altitude whenever the current altitude exceeds the previous maximum.
State & Boundaries
Initialize altitude and highest altitude to zero to correctly handle cases where all gains are negative or zero.
Common Pitfalls & Bugs
Failing to initialize highest altitude to zero can cause incorrect results if the highest altitude is the starting point before any gains.
Complexity
This approach achieves O(n) time and O(1) auxiliary space by avoiding nested loops and extra data structures.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
altitude += changeUpdate the current altitude by adding the current gain.
This running total reflects the altitude at the current point, avoiding repeated summations and enabling efficient tracking.
highest = max(highest, altitude)Update the highest altitude if the current altitude exceeds it.
Tracking the maximum altitude during iteration ensures the algorithm returns the correct highest altitude without extra passes or storage.
Full line-by-line criticality + rationale for all 6 lines available on Pro.
Test Your Understanding
Why is it sufficient to track the running altitude and update the highest altitude in a single pass rather than computing all altitudes first?
See the answer with Pro.
Related Problems
Prefix Sum pattern
Don't just read it. Drill it.
Reconstruct Find the Highest Altitude from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Find the Highest Altitude drill