Find the Highest Altitude - Solution & Explanation
Problem Statement
There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.
You are given an integer array gain of length n where gain[i] is the net gain in altitude between points iāāāāāā and i + 1 for all (0 <= i < n). Return the highest altitude of a point.
Example 1:
Input: gain = [-5,1,5,0,-7] Output: 1 Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.
Example 2:
Input: gain = [-4,-3,-2,-1,4,3,2] Output: 0 Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.
Constraints:
n == gain.length1 <= n <= 100-100 <= gain[i] <= 100
Approach Overview
Problem Overview: You start a bike trip at altitude 0. The array gain[i] represents the net altitude change between point i and i+1. The task is to compute the altitude after each step and return the highest altitude reached during the trip.
Approach 1: Recompute Altitude for Each Position (Brute Force) (Time: O(nĀ²), Space: O(1))
A straightforward approach calculates the altitude at each checkpoint by summing all previous gains. For index i, iterate from 0 to i and accumulate the altitude change. Track the maximum altitude seen so far while repeating this process for every position. This works because altitude is simply the sum of gains up to that point. However, the repeated summation causes redundant work, resulting in O(nĀ²) time. This method is rarely used in practice but helps illustrate the transition to a prefix-based optimization.
Approach 2: Cumulative Altitude Calculation (Prefix Sum) (Time: O(n), Space: O(1))
The optimal approach treats altitude as a running prefix sum. Start with currentAltitude = 0 since the biker begins at sea level. Iterate through the gain array once. For each value, update the altitude using currentAltitude += gain[i] and update the maximum altitude using maxAltitude = max(maxAltitude, currentAltitude). Because the altitude at step i depends only on the previous altitude plus the current gain, you never need to recompute earlier values.
This technique is a classic application of the Prefix Sum pattern. Instead of storing the entire prefix array, you maintain only the current cumulative value and the best result seen so far. The algorithm scans the array once, performs constant-time updates, and uses only two variables.
The input structure is a simple Array, so sequential traversal is sufficient. Each element represents the difference between consecutive altitudes rather than the altitude itself, which makes the cumulative approach the natural fit.
Recommended for interviews: Interviewers expect the cumulative altitude (prefix sum) approach. It demonstrates that you recognize incremental state updates and avoid redundant recomputation. Mentioning the brute-force idea briefly shows understanding of the underlying definition of altitude, but implementing the O(n) running-sum solution shows strong problem-solving instincts and familiarity with the prefix sum pattern.
Approach 1: Cumulative Altitude Calculation
To solve the problem, calculate the altitude at each point by starting from altitude 0 and adding up the values from the 'gain' array. This involves iterating through the array and keeping track of the current altitude. At each step, update and compare against the maximum altitude to find the highest point reached during the entire trip.
The function highestAltitude initializes the altitude to 0. It then iterates through the array 'gain', updating the current altitude by adding each 'gain[i]' and simultaneously checking if this new altitude is the highest so far. The highest recorded altitude is returned.
Complexity
Time Complexity: O(n), where n is the length of the gain array, as we iterate through the gain array once.
Space Complexity: O(1), as no extra space proportional to input size is used.
Approach 2: Prefix Sum (Difference Array)
We assume the altitude of each point is h_i. Since gain[i] represents the altitude difference between the ith point and the (i + 1)th point, we have gain[i] = h_{i + 1} - h_i. Therefore:
$
sum_{i = 0}^{n-1} gain[i] = h_1 - h_0 + h_2 - h_1 + cdots + h_n - h_{n - 1} = h_n - h_0 = h_n
which implies:
h_{i+1} = sum_{j = 0}^{i} gain[j]
We can see that the altitude of each point can be calculated through the prefix sum. Therefore, we only need to traverse the array once, find the maximum value of the prefix sum, which is the highest altitude.
In fact, the gain
array in the problem is a difference array. The prefix sum of the difference array gives the original altitude array. Then find the maximum value of the original altitude array.
The time complexity is O(n), and the space complexity is O(1). Here, n$ is the length of the array gain.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Cumulative Altitude Calculation | Time Complexity: O(n), where n is the length of the gain array, as we iterate through the gain array once. |
| Prefix Sum (Difference Array) | ā |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recompute Altitude for Each Position (Brute Force) | O(nĀ²) | O(1) | Conceptual baseline to understand altitude as cumulative gain |
| Cumulative Altitude Calculation (Prefix Sum) | O(n) | O(1) | Best approach for interviews and production; single pass with constant memory |
Video Solution
1732 Find the Highest Altitude | Zero to FAANG Kunal | Assignment Solution | Leetcode ā¢ Programmers Zone ā¢ 9,014 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Find the Highest Altitude easy or hard?
How to solve Find the Highest Altitude in O(n)?
Find the Highest Altitude Python or Java solution?
What is the best approach for Find the Highest Altitude?
Is Find the Highest Altitude asked at Google/Amazon/Meta?
What data structure is used in Find the Highest Altitude?
What is the time complexity of Find the Highest Altitude?
Ready to solve this problem?
Practice Find the Highest Altitude with our built-in code editor and test cases.
Practice on FleetCode