LeetCode 1732 - Find the Highest Altitude

LeetCode Problem 1732

Difficulty: 🟢 Easy
Topics: Array, Prefix Sum

Solution

Problem Understanding

In this problem, a biker starts at altitude 0 and travels through a sequence of roads. The input array gain describes how the biker's altitude changes between consecutive points on the trip.

If gain[i] is positive, the biker climbs upward between point i and point i + 1. If it is negative, the biker descends. The actual altitude at each point is determined by cumulatively applying these altitude changes.

The task is to compute the highest altitude reached at any point during the trip.

For example, if:

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

then the altitudes become:

Start: 0
After -5: -5
After +1: -4
After +5: 1
After +0: 1
After -7: -6

The highest altitude reached is 1.

The input array has length n, meaning there are n + 1 altitude points. Since the biker starts at altitude 0, we can think of the problem as building a running total and tracking the maximum value encountered.

The constraints are small:

• 1 <= n <= 100
• -100 <= gain[i] <= 100

These constraints tell us that performance is not a major concern. Even a less efficient solution would pass. However, the problem is fundamentally a prefix sum problem, and there is a very clean linear-time solution.

Several edge cases are important:

• All altitude gains may be negative, meaning the biker never rises above the starting altitude.
• The highest altitude may occur at the starting point itself.
• Multiple consecutive gains may produce the same maximum altitude.
• The array contains only one element, which is the smallest possible input size.

Because the biker always starts at altitude 0, the answer can never be less than 0.

Approaches

Brute Force Approach

A brute-force solution would explicitly construct the full altitude array.

We start with altitude 0, then repeatedly apply each gain value to compute the next altitude. After building the entire list of altitudes, we scan the list to find the maximum value.

For example:

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

altitudes:
[0, -5, -4, 1, 1, -6]

Then we return the maximum altitude from this array.

This approach is correct because every altitude is computed exactly according to the problem definition. However, it uses extra space to store all intermediate altitudes, even though we only need the current altitude and the maximum altitude seen so far.

Optimal Approach

The key observation is that we do not need to store every altitude.

At any point in time, we only need:

• The current altitude
• The highest altitude encountered so far

As we iterate through gain, we continuously update the running altitude using prefix sums. After each update, we compare the current altitude against the maximum altitude.

This works because each altitude depends only on the previous altitude and the current gain value.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Builds the full altitude array before finding the maximum
Optimal	O(n)	O(1)	Uses a running prefix sum and tracks the maximum directly

Algorithm Walkthrough

1. Initialize two variables:

• current_altitude = 0
• highest_altitude = 0

The biker starts at altitude 0, so both variables begin there. 2. Iterate through each value in the gain array. 3. For each gain value:

• Add it to current_altitude
• This computes the biker's new altitude after traveling to the next point.

4. Compare current_altitude with highest_altitude.
5. If the current altitude is greater, update highest_altitude.
6. Continue until all gain values have been processed.
7. Return highest_altitude.

Why it works

The algorithm maintains an important invariant:

• current_altitude always represents the biker's altitude after processing the current segment.
• highest_altitude always stores the maximum altitude seen so far.

Since every altitude is generated exactly once through the running prefix sum, and every altitude is compared against the maximum, the final result must be the highest altitude reached during the trip.

Python Solution

from typing import List

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        current_altitude = 0
        highest_altitude = 0

        for altitude_gain in gain:
            current_altitude += altitude_gain
            highest_altitude = max(highest_altitude, current_altitude)

        return highest_altitude

The implementation follows the optimal prefix sum approach directly.

The variable current_altitude stores the biker's altitude after each road segment. Each element in gain is added to this running total.

The variable highest_altitude tracks the maximum altitude encountered so far. After updating the current altitude, we compare it against the current maximum using max().

The algorithm processes the array in a single pass and does not allocate any extra data structures proportional to the input size.

Go Solution

func largestAltitude(gain []int) int {
    currentAltitude := 0
    highestAltitude := 0

    for _, altitudeGain := range gain {
        currentAltitude += altitudeGain

        if currentAltitude > highestAltitude {
            highestAltitude = currentAltitude
        }
    }

    return highestAltitude
}

The Go implementation mirrors the Python solution closely.

Go does not provide a built-in max() function for integers in the standard language syntax, so we use a simple if statement to update highestAltitude.

No special handling is needed for empty input because the problem guarantees that gain.length >= 1.

Integer overflow is also not a concern because the constraints are very small.

Worked Examples

Example 1

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

Initial state:

current_altitude = 0
highest_altitude = 0

Step	gain[i]	Current Altitude	Highest Altitude
Start	-	0	0
1	-5	-5	0
2	1	-4	0
3	5	1	1
4	0	1	1
5	-7	-6	1

Final answer:

1

Example 2

gain = [-4,-3,-2,-1,4,3,2]

Initial state:

current_altitude = 0
highest_altitude = 0

Step	gain[i]	Current Altitude	Highest Altitude
Start	-	0	0
1	-4	-4	0
2	-3	-7	0
3	-2	-9	0
4	-1	-10	0
5	4	-6	0
6	3	-3	0
7	2	-1	0

Final answer:

0

The biker never climbs above the starting altitude.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is traversed exactly once
Space	O(1)	Only a few variables are used

The algorithm performs one pass through the input array, so the running time grows linearly with the number of elements.

The memory usage remains constant because we only store two integer variables regardless of input size.

Test Cases

from typing import List

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        current_altitude = 0
        highest_altitude = 0

        for altitude_gain in gain:
            current_altitude += altitude_gain
            highest_altitude = max(highest_altitude, current_altitude)

        return highest_altitude

solution = Solution()

assert solution.largestAltitude([-5, 1, 5, 0, -7]) == 1
# Standard mixed gains example

assert solution.largestAltitude([-4, -3, -2, -1, 4, 3, 2]) == 0
# Highest altitude remains the starting altitude

assert solution.largestAltitude([5]) == 5
# Single positive gain

assert solution.largestAltitude([-5]) == 0
# Single negative gain, starting altitude is highest

assert solution.largestAltitude([1, 2, 3]) == 6
# Strictly increasing altitude

assert solution.largestAltitude([-1, -2, -3]) == 0
# Strictly decreasing altitude

assert solution.largestAltitude([0, 0, 0]) == 0
# No altitude changes

assert solution.largestAltitude([3, -1, 2, -2, 4]) == 6
# Maximum occurs near the end

assert solution.largestAltitude([10, -10, 10, -10]) == 10
# Multiple visits to the same maximum altitude

assert solution.largestAltitude([100] * 100) == 10000
# Maximum constraint-style positive accumulation

Test Summary

Test	Why
[-5,1,5,0,-7]	Verifies standard mixed positive and negative gains
[-4,-3,-2,-1,4,3,2]	Ensures starting altitude can remain the maximum
[5]	Smallest input with positive gain
[-5]	Smallest input with negative gain
[1,2,3]	Tests continuous upward movement
[-1,-2,-3]	Tests continuous downward movement
[0,0,0]	Ensures zero changes are handled correctly
[3,-1,2,-2,4]	Tests fluctuating altitudes
[10,-10,10,-10]	Tests repeated maximum values
[100] * 100	Stress-style test using maximum constraints

Edge Cases

One important edge case occurs when all gains are negative. In this situation, the biker continuously loses altitude and never rises above the starting point. A buggy implementation might incorrectly initialize the maximum altitude to a very small number or fail to consider the starting altitude itself. This implementation correctly initializes highest_altitude to 0, ensuring the starting point is always considered.

Another important case is when the input contains only one element. Since the minimum array size is 1, the algorithm must still work correctly for a single road segment. The implementation handles this naturally because the loop processes exactly one value and updates the running altitude once.

A third edge case occurs when multiple altitudes tie for the highest value. For example:

gain = [2, -2, 2, -2]

The biker reaches altitude 2 multiple times. The implementation correctly keeps the maximum value unchanged once it has already been reached.

A final edge case involves all zero values. In this scenario, the biker never changes altitude. The running altitude remains 0 throughout the computation, and the algorithm correctly returns 0.