Domain 1EasyCORE

Find the Highest Altitude

The problem involves calculating the highest altitude reached by a biker during a road trip. The biker starts at point 0 with an altitude of 0. We are given an array `gain` where each element represents the net gain in altitude between consecutive points. The task is to return the highest altitude encountered during the trip.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

1732. Find the Highest Altitude

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 79.9%


Problem Breakdown

The problem involves calculating the highest altitude reached by a biker during a road trip. The biker starts at point 0 with an altitude of 0. We are given an array gain where each element represents the net gain in altitude between consecutive points. The task is to return the highest altitude encountered during the trip.

Inputs:

  • An integer array gain of length n, where 1 <= n <= 100.
  • Each element in gain is an integer representing the net gain in altitude between two consecutive points, with -100 <= gain[i] <= 100.

Outputs:

  • An integer representing the highest altitude reached during the trip.

Implicit Constraints/Edge Cases:

  • The array gain can contain negative values, indicating a decrease in altitude.
  • The array gain can contain zeros, indicating no change in altitude.
  • The starting altitude is always 0.
  • If all gains are negative, the highest altitude will be 0.

Intuition

To solve this problem, we need to calculate the altitude at each point and keep track of the maximum altitude encountered. A brute-force approach would involve iterating through the gain array, calculating the altitude at each step, and updating the maximum altitude if the current altitude is higher than the previously recorded maximum. This approach has a time complexity of O(n) and a space complexity of O(1), which is efficient enough given the constraints.

The key insight here is that we don’t need to store all the altitudes; we only need to keep track of the current altitude and update the maximum altitude as we iterate through the gain array. This approach avoids unnecessary memory usage and maintains a linear time complexity.

Approach

  1. Initialize two variables: current_altitude to 0 (starting altitude) and max_altitude to 0 (initially, the highest altitude is 0).
  2. Iterate through each element in the gain array.
  3. For each element, update the current_altitude by adding the gain value.
  4. If the updated current_altitude is greater than max_altitude, update max_altitude.
  5. After iterating through all elements, return max_altitude.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the gain array. We iterate through the array once.
  • Space Complexity: O(1). We use a constant amount of extra space for variables.

Solution

def largestAltitude(gain):
    current_altitude = 0
    max_altitude = 0
    
    for g in gain:
        current_altitude += g
        if current_altitude > max_altitude:
            max_altitude = current_altitude
    
    return max_altitude

Edge Cases Handled

  • All negative gains: If all values in gain are negative, the highest altitude will be 0.
  • All zeros in gain: The altitude remains constant at 0 throughout the trip.
  • Mixed positive and negative gains: The algorithm correctly calculates the highest altitude by considering both increases and decreases in altitude.