Find the Highest Altitude

Find the Highest Altitude

What is this problem about?

The Find the Highest Altitude interview question is a simple tracking task. You start a bike trip at altitude 0. You are given an array gain where gain[i] is the net altitude gain/loss between points $i$ and $i+1$. You need to find the highest altitude reached at any point during the trip.

Why is this asked in interviews?

Companies like Meta and Amazon use this as a warm-up coding question. It tests a candidate's basic understanding of the Prefix Sum interview pattern and their ability to maintain a running maximum. It’s an essential "check" for programming fundamentals.

Algorithmic pattern used

This problem follows the Prefix Sum and Running Maximum patterns.

1. Initialize: currentAltitude = 0, maxAltitude = 0.
2. Iterate: Loop through each value in the gain array.
3. Update State:

• Add the current gain to currentAltitude.
• Update maxAltitude if currentAltitude is larger.

1. Return: The maxAltitude.

Example explanation

Gains: [-5, 1, 5, 0, -2]

• Start: altitude 0. max = 0.
• Point 1: $0 + (-5) = -5$. max = 0.
• Point 2: $-5 + 1 = -4$. max = 0.
• Point 3: $-4 + 5 = 1$. max = 1.
• Point 4: $1 + 0 = 1$. max = 1.
• Point 5: $1 + (-2) = -1$. max = 1. The highest altitude reached is 1.

Common mistakes candidates make

• Starting at the wrong point: Forgetting that the trip starts at altitude 0 before the first gain is applied.
• Missing the initial 0: If all gains are negative, the highest altitude is the starting point (0), not the first point in the trip.
• Using an array: Creating a full prefix sum array when only two variables (current and max) are needed ($O(1)$ space).

Interview preparation tip

Always look for ways to optimize space. If you only need to compare the "current" total with a "best" total, you don't need to store all the intermediate totals in a list. This shows a "production-ready" mindset.