Find the Highest Altitude: Prefix Sum Basics

A biker goes on a road trip through n + 1 points at different altitudes. You start at altitude 0, and you are given an integer array gain where gain[i] is the net altitude change between point i and point i + 1. Return the highest altitude reached at any point.

This is LeetCode 1732: Find the Highest Altitude, and it is one of the cleanest introductions to the prefix sum pattern you will find. The problem is rated easy, but the underlying idea, computing a running total and tracking its maximum, is a building block that powers dozens of harder problems.

Why this problem matters

At first glance, this looks almost too simple. You just add up numbers and remember the biggest one. But that simplicity is exactly the point. This problem isolates the prefix sum pattern in its purest form, without any extra complexity layered on top.

Prefix sums show up everywhere in interview problems. Range sum queries, subarray sum problems, and even certain two-pointer techniques all rely on the same core idea: instead of recomputing a sum from scratch every time, you build it incrementally. If you drill this pattern until it is automatic, you will recognize it instantly when it appears inside a harder problem.

The other reason this problem matters is that it teaches you to think about "what values exist along the way" rather than just "what is the final answer." The gain array tells you the changes, but the question asks about the altitudes themselves. Translating from deltas to absolute values is a skill that transfers to problems involving cumulative frequencies, balance tracking, and net flow calculations.

The key insight

The gain array gives you differences between consecutive altitudes. To recover the actual altitudes, you compute a running total (prefix sum) of the gain values. The altitude at point i is the sum of gain[0] through gain[i-1], with the starting altitude of 0.

You do not need to store all the altitudes. You only need two things: the current altitude (your running total) and the maximum altitude seen so far. One pass through the array, and you are done.

The solution

def largest_altitude(gain):
    current = 0
    highest = 0

    for g in gain:
        current += g
        highest = max(highest, current)

    return highest

The function starts with current = 0 because the biker begins at altitude 0. For each gain value, it updates the running altitude and checks whether this new altitude is the highest seen so far. At the end, highest holds the answer.

Notice that highest also starts at 0. This is important because the starting point itself (altitude 0) could be the highest point if all the gains are negative.

Visual walkthrough

Each step adds one gain value to the running total and checks whether we have a new maximum. The highest altitude we encounter is 1, which occurs at points 3 and 4.

Complexity analysis

Time: O(n). You visit each element in the gain array exactly once. Each visit does O(1) work: one addition and one comparison. Total: O(n) where n is the length of the gain array.

Space: O(1). You only use two variables (current and highest), regardless of how large the input is. No extra arrays or data structures needed.

This is optimal. You must look at every gain value at least once (the answer could depend on any of them), so you cannot do better than O(n). And O(1) space means zero overhead beyond the input itself.

The building blocks

1. Prefix sum accumulation

The act of maintaining a running total as you iterate through an array. You start with an initial value and add each element to it. This is the same pattern used in Running Sum of 1d Array, except here you do not need to store every intermediate sum.

current = 0
for value in array:
    current += value

This micro-pattern is the foundation of range sum queries, cumulative frequency tables, and any problem where you need to convert deltas into absolute values.

2. Running max tracking

While building the prefix sum, you simultaneously track the largest value you have seen. This is the same idea as tracking the running minimum in Best Time to Buy and Sell Stock, just in the opposite direction.

best = initial_value
for value in sequence:
    best = max(best, value)

Combining a prefix sum with a running max (or min) is a pattern that recurs in problems like Maximum Subarray, where you track the best prefix sum minus the worst earlier prefix sum.

Edge cases

• All negative gains like [-4, -3, -2, -1, -5]: the altitudes are [0, -4, -7, -9, -10, -15]. The highest is 0 (the start). Make sure you initialize highest = 0 to catch this.
• All positive gains like [1, 2, 3]: the altitudes keep climbing. The last altitude is the highest, which is 6.
• Single element [5]: altitudes are [0, 5]. The highest is 5.

From understanding to recall

You have just walked through the cleanest possible prefix sum problem. The logic is simple: accumulate a running total, track the max. But will you remember the initialization detail (starting both current and highest at 0) when you see this pattern buried inside a harder problem two weeks from now?

That is where spaced repetition helps. Instead of solving this once and moving on, you revisit the prefix sum accumulation and running max tracking patterns at increasing intervals. Each time you write the code from memory. After a few reps, these two building blocks fire automatically whenever you see a problem that involves cumulative values.

Related posts

• Running Sum of 1d Array - Direct prefix sum application, the same accumulation pattern without the max tracking
• Maximum Subarray - Kadane's algorithm uses prefix sum thinking to find the best contiguous subarray
• Best Time to Buy and Sell Stock - Running min tracking, the mirror image of the running max used here

Find the Highest Altitude is a warm-up, but the two building blocks it teaches (prefix sum accumulation and running max tracking) are anything but trivial. They combine and recombine across dozens of array problems. Learning them here in isolation means you will recognize them instantly when they appear in a more complex context. That is the CodeBricks approach: master the bricks, and the walls build themselves.