1732. Find the Highest Altitude

Time: O(n)

Space: O(1)

Problem Overview

The biker begins at altitude 0 before any road segment.

Intuition

The biker begins at altitude 0 before any road segment. Each gain[i] adds to the current altitude — that is a prefix sum over the gain array. The highest altitude is the maximum prefix sum encountered, including the starting altitude 0 before the first segment.

Algorithm

1Set ans = 0 and currAltitude = 0 (starting point).
2For each g in gain: add g to currAltitude.
3Update ans = max(ans, currAltitude) after each step.
4Return ans.

Example Walkthrough

Input: gain = [-5, 1, 5, 0, -7]

1.Start at altitude 0 → ans = 0.
2.After -5 → altitude -5 → ans still 0.
3.After +1 → altitude -4.
4.After +5 → altitude 1 → ans = 1.
5.After 0 → altitude 1.
6.After -7 → altitude -6.

Output: 1

Common Pitfalls

•Initialize ans to 0 — the answer can be 0 if the biker never climbs above the start.
•Update the maximum after each gain, not only at the end.
•Do not assume the peak is at the last index.

1732.cs

// Approach: The biker starts at altitude 0. Each gain[i] updates the current altitude.
// Track the running sum (prefix sum of gain) and keep the maximum altitude seen at any step, including the start.
// Time: O(n) Space: O(1)
public class Solution
{
    public int LargestAltitude(int[] gain)
    {
        int ans = 0;
        int currAltitude = 0;
        foreach (int g in gain)
        {
            currAltitude += g;
            ans = Math.Max(ans, currAltitude);
        }
        return ans;
    }
}

Was this solution helpful?