Find the Highest Altitude - Video Solutions

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.