Find the Highest Altitude solution and explanation
Google
9 more videos on this problem
1732 Find the Highest Altitude | Zero to FAANG Kunal | Assignment Solution | LeetcodeProgrammers Zone · 10:20 · 9K views
Leetcode 1732 | Find the Highest Altitude | 18th from LC 75 | 90 Days SE PrepPepcoding · 1:28 · 4K views
Leetcode | 1732. Find the Highest Altitude | Easy | Java SolutionDeveloper Docs · 3:46 · 3K views
Find the Highest Altitude - LeetCode 1732 - Python #leetcode #leetcode75Deepti Talesra · 4:24 · 3K views
Leetcode Solution - 1732 Find the Highest AltitudeJohn Leonardo · 2:48 · 2K views
1732 Find the Highest Altitude LeetCode Problem in C++ | LeetCode for Beginners | LeetCode SolutionCoding enthusiast · 4:30 · 1K views
1732 Find the Highest Altitude with Python | Leetcode Python #pythontutorial #leetcode #youtubeArsalan Ahmed · 6:55 · 575 views
Find the Highest Altitude | leetcode 1732 | Array Coding QuestionsCodeMap · 3:30 · 466 views
Python Programming - Find the Highest Altitude | JavaScript, Java and C++ | LeetCode #1732CodingNinja · 2:33 · 431 views
Daily Leetcode #1175: Jun 19, 2023 - 1732. Find the Highest AltitudeProgramming Live with Larry · 2:30 · 411 views
The problem
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.
def highest_altitude(gain):
max_altitude = 0
current_altitude = 0
for g in gain:
current_altitude += g
if current_altitude > max_altitude:
max_altitude = current_altitude
return max_altitude
print(highest_altitude([-5, 1, 5, 0, -7]))public class HighestAltitude {
public static int highestAltitude(int[] gain) {
int maxAltitude = 0;
int currentAltitude = 0;
for (int g : gain) {
currentAltitude += g;
if (currentAltitude > maxAltitude) {
maxAltitude = currentAltitude;
}
}
return maxAltitude;
}
public static void main(String[] args) {
int[] gain = {-5, 1, 5, 0, -7};
System.out.println(highestAltitude(gain));
}
}#include <vector>
#include <iostream>
int highestAltitude(std::vector<int>& gain) {
int max_altitude = 0;
int current_altitude = 0;
for (int g : gain) {
current_altitude += g;
max_altitude = std::max(max_altitude, current_altitude);
}
return max_altitude;
}
int main() {
std::vector<int> gain = {-5, 1, 5, 0, -7};
std::cout << highestAltitude(gain);
return 0;
}function highestAltitude(gain) {
let maxAltitude = 0;
let currentAltitude = 0;
for (let i = 0; i < gain.length; i++) {
currentAltitude += gain[i];
if (currentAltitude > maxAltitude) {
maxAltitude = currentAltitude;
}
}
return maxAltitude;
}
console.log(highestAltitude([-5, 1, 5, 0, -7]));#include <stdio.h>
int highestAltitude(int* gain, int n) {
int max_altitude = 0;
int current_altitude = 0;
for (int i = 0; i < n; i++) {
current_altitude += gain[i];
if (current_altitude > max_altitude) {
max_altitude = current_altitude;
}
}
return max_altitude;
}
int main() {
int gain[] = {-5, 1, 5, 0, -7};
int n = sizeof(gain) / sizeof(gain[0]);
printf("%d", highestAltitude(gain, n));
return 0;
}using System;
public class Program {
public static int HighestAltitude(int[] gain) {
int maxAltitude = 0;
int currentAltitude = 0;
foreach (int g in gain) {
currentAltitude += g;
if (currentAltitude > maxAltitude) {
maxAltitude = currentAltitude;
}
}
return maxAltitude;
}
public static void Main() {
int[] gain = {-5, 1, 5, 0, -7};
Console.WriteLine(HighestAltitude(gain));
}
}This Python function keeps track of the current altitude while traversing the gain list. The maximum altitude is updated whenever the current altitude surpasses it, ensuring that the highest point is recorded upon completion.
Time Complexity: O(n), due to single pass through the gain list.
Space Complexity: O(1), consuming constant memory space.
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.
func largestAltitude(gain []int) (ans int) {
h := 0
for _, v := range gain {
h += v
if ans < h {
ans = h
}
}
return
}impl Solution {
pub fn largest_altitude(gain: Vec<i32>) -> i32 {
let mut ans = 0;
let mut h = 0;
for v in gain.iter() {
h += v;
ans = ans.max(h);
}
ans
}
}class Solution {
/**
* @param Integer[] $gain
* @return Integer
*/
function largestAltitude($gain) {
$max = 0;
for ($i = 0; $i < count($gain); $i++) {
$tmp += $gain[$i];
if ($tmp > $max) {
$max = $tmp;
}
}
return $max;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Cumulative Altitude Calculation | Time Complexity: O(n), due to single pass through the gain list. |
| Prefix Sum (Difference Array) | – |
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 |
Frequently asked questions
Is Find the Highest Altitude easy or hard?
Find the Highest Altitude is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge mainly tests whether you recognize that altitude is the cumulative sum of gains and that the maximum prefix value represents the highest altitude reached.
How to solve Find the Highest Altitude in O(n)?
Initialize two variables: currentAltitude = 0 and maxAltitude = 0. Iterate through the gain array and update the running altitude with currentAltitude += gain[i]. After each update, compare it with maxAltitude and store the larger value. The final maxAltitude represents the highest point reached during the trip.
Find the Highest Altitude Python or Java solution?
The logic is identical across languages. Iterate through the gain array, keep a running sum representing the current altitude, and update a maximum variable. Python, Java, C++, JavaScript, and C# implementations all follow this same O(n) prefix-sum pattern.
What is the best approach for Find the Highest Altitude?
The best approach is a cumulative altitude calculation using the prefix sum pattern. Start at altitude 0, iterate through the gain array, and keep a running sum while tracking the maximum altitude reached. This solution runs in O(n) time and O(1) space because it processes each gain once and stores only the current and maximum altitude.
Is Find the Highest Altitude asked at Google/Amazon/Meta?
Find the Highest Altitude is an easy-level problem commonly used for screening rounds and practice. Variations of prefix sum and cumulative tracking frequently appear in interviews at companies like Amazon, Google, and Meta because they test understanding of array traversal and running aggregates.
What data structure is used in Find the Highest Altitude?
The problem uses a simple array to represent altitude differences between consecutive checkpoints. The algorithm processes the array sequentially while maintaining a running prefix sum. No additional data structures are required beyond a couple of integer variables.
What is the time complexity of Find the Highest Altitude?
The optimal solution runs in O(n) time where n is the length of the gain array. Each element is processed exactly once while updating a running altitude and the maximum altitude seen so far. Space complexity is O(1) because only a few variables are required.