Find the Highest Altitude in Python – LeetCode75 Explained

The Find the Highest Altitude problem from LeetCode75 is a beginner-friendly question that tests your ability to work with prefix sums and arrays. It’s a common warm-up problem in coding interviews, especially for testing iteration logic and cumulative calculations.

In this blog, we’ll break down the problem, walk through examples and explain a clean Python solution step by step.

Problem Statement

You are given an integer array gain where gain[i] represents the net gain in altitude between two points on a bike trip. The starting altitude is always 0.

Return the highest altitude reached during the trip.

Understanding the Problem

Starting altitude = 0
Each element in gain represents how much altitude is gained or lost.
We keep a running total of altitude.
The highest value seen during the trip is our answer.

This is essentially a prefix sum problem: we keep adding each gain to the running total and track the maximum.

Examples

Example 1:

Input: gain = [-5, 1, 5, 0, -7]  
Output: 1  

Explanation:  
Starting altitude = 0  
Step 1: 0 + (-5) = -5  
Step 2: -5 + 1 = -4  
Step 3: -4 + 5 = 1  -- highest altitude  
Step 4: 1 + 0 = 1  
Step 5: 1 + (-7) = -6  
Maximum altitude reached = 1

Example 2:

Input: gain = [-4, -3, -2, -1, 4, 3, 2]  
Output: 0  

Explanation: The path only goes down and comes back to 0, so the highest altitude is the starting point.

Python Solution – Step by Step

Here’s the clean Python implementation:

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        current_altitude = 0
        max_altitude = 0

        for altitude_gain in gain:
            # Step 2: Update the running altitude
            current_altitude += altitude_gain
            # Step 3: Track the maximum altitude
            max_altitude = max(max_altitude, current_altitude)

        return max_altitude

Step 1: Initialize Altitudes

current_altitude = 0
max_altitude = 0

Start from altitude 0.
Keep track of the highest altitude seen so far.

Step 2: Traverse the Gain Array

for altitude_gain in gain:
    current_altitude += altitude_gain

Add each altitude_gain to the running altitude.

Step 3: Update Maximum Altitude

max_altitude = max(max_altitude, current_altitude)

Compare the current altitude with the max altitude seen so far.

Step 4: Return the Result

return max_altitude

After completing the loop, return the highest altitude.

Why This Solution Works

It uses a prefix sum approach.
Each step is just an O(1) update.
We only need two variables (current_altitude and max_altitude).

Time and Space Complexity

Time Complexity: O(n) → We loop through the gain array once.
Space Complexity: O(1) → Only variables for current and maximum altitude.

Edge Cases to Consider

Input	Output	Explanation
`gain = [0,0,0]`	`0`	Altitude never changes.
`gain = [-5,-10]`	`0`	Always goes down, starting point is the max.
`gain = [10,5,-2,7]`	`20`	Highest reached before going down.

Real-World Applications

Tracking elevations in GPS or biking apps.
Finance: Tracking maximum profit from cumulative gains and losses.
Sensor data analysis: Monitoring peak levels in streams of values.

Conclusion

The Find the Highest Altitude problem is a simple yet powerful exercise in prefix sums. It helps build intuition for cumulative tracking problems which appear often in data analysis and interview questions.

By maintaining a running total and updating the maximum, we solve the problem efficiently in O(n) time and O(1) space.