Highest Altitude LeetCode 1732 Guide

LeetCode 1732 Find the Highest Altitude gives you a biker who starts at altitude 0 and takes a road trip across n+1 points. You are given a gain array of length n where gain[i] is the net altitude change between point i and point i+1.

Your task is to find the highest altitude reached at any point along the entire route including the starting point. The biker begins at altitude 0, which is itself a valid candidate for the highest altitude if all gains are negative.

Because gain[i] is a net change and not an absolute altitude, you must accumulate the gains to recover each point's altitude. The problem is fundamentally asking for the maximum value in the altitude prefix sum array.

The altitude at point i equals the sum of gain[0] through gain[i-1] — that is, the prefix sum of the gain array up to index i-1. Computing all n+1 altitudes naively would use O(n) space for the altitude array, but you only need the maximum, so a running accumulator suffices.

As you iterate through the gain array left to right, maintain a running altitude variable that accumulates each gain. After applying each gain, compare the running altitude to a tracked maximum and update if necessary. This is prefix sum combined with max tracking in a single pass.

Because the starting altitude of 0 must also be considered, initialize maxAlt = 0 before the loop begins. This ensures that if all gains are negative and every altitude after the start is below zero, the answer is still 0 — the starting point.

The algorithm uses two variables: altitude tracks the current elevation and maxAlt tracks the highest seen so far. Both start at 0 — altitude because the biker starts there, and maxAlt because 0 is a valid answer if all gains are negative.

For each gain value in the array, add it to altitude to get the elevation at the next point. Then update maxAlt if the new altitude exceeds it. After processing all gains, maxAlt holds the answer.

This is strictly O(n) time and O(1) space. There is no sorting, no hash map, and no stack. The entire solution can be written in three lines of code after initialization.

The biker starts at altitude 0. This is not just a setup detail — it means the altitude array always begins with 0 regardless of the gain values. If all gains are negative, every subsequent altitude is below 0, and the highest point on the entire route is the starting altitude of 0.

This is why you initialize maxAlt = 0 rather than negative infinity. Initializing to -infinity would work only if you explicitly include 0 in your comparison loop. Initializing to 0 implicitly includes the starting altitude as a candidate without adding any extra code.

In interview settings, forgetting the starting altitude is the most common mistake on this problem. The gain array has n elements but the route has n+1 points. The answer must account for all n+1 altitudes, not just the n values produced by accumulating gains.

Example 1 — gain = [-5, 1, 5, 0, -7]: Starting altitude is 0. After gain -5: altitude = -5. After gain 1: altitude = -4. After gain 5: altitude = 1. After gain 0: altitude = 1. After gain -7: altitude = -6. The altitude sequence is [0, -5, -4, 1, 1, -6]. Maximum = 1.

Example 2 — gain = [-4, -3, -2, -1, 4, 3, 2]: Altitude sequence: 0, -4, -7, -9, -10, -6, -3, -1. All post-start altitudes are negative. The maximum is 0 — the starting altitude. This confirms why initializing maxAlt = 0 is essential.

Notice that in Example 2 the gains eventually go positive (4, 3, 2) but the accumulation never climbs back above the starting point. The answer is 0, not 9 (the sum of the positive gains) — the prefix sum captures the full picture.

Python implementation using a manual loop: altitude = maxAlt = 0; for g in gain: altitude += g; maxAlt = max(maxAlt, altitude); return maxAlt. Four lines of logic. Python one-liner using itertools.accumulate: return max(0, max(itertools.accumulate(gain))). Both are O(n) time and O(1) or O(n) space depending on whether accumulate materializes a list.

Java implementation: int altitude = 0, maxAlt = 0; for (int g : gain) { altitude += g; maxAlt = Math.max(maxAlt, altitude); } return maxAlt. Identical structure to Python. No auxiliary data structures, single loop, constant extra space.

Both implementations share the same invariant: maxAlt is initialized to 0 (not Integer.MIN_VALUE or float('-inf')), and the loop updates altitude before comparing. The order matters — altitude must be updated to the post-gain value before taking the max.

Find the Highest Altitude belongs to the prefix sum family — problems where accumulated running totals reveal hidden structure. Find Pivot Index (LeetCode 724) uses prefix sums from both ends to find a balance point. Range Sum Query (LeetCode 303) precomputes prefix sums for O(1) range queries. All three reward the same mental model: build running totals, query them efficiently.

Count Vowel Strings in Ranges (LeetCode 2559) applies prefix sums to string properties rather than numbers, showing the pattern generalizes beyond pure arithmetic. Running Sum of 1d Array (LeetCode 1480) is essentially this exact operation — accumulate in place — making it a perfect companion problem.

For interview preparation, mastering the prefix sum pattern unlocks a wide class of subarray and range problems. The key insight is always the same: precompute accumulated values so that any range query or running property can be answered in O(1) after an O(n) setup pass.