Vultr DocsLatest Content

Find the Highest Altitude

Updated on 28 May, 2025
Find the Highest Altitude header image

Problem Statement

Imagine a biker embarking on a scenic road trip that consists of multiple points, each at varying altitudes. Starting from point 0 at sea level (altitude 0), the elevation at each subsequent point can either increase or decrease based on a given set of gains or losses. The biker's journey is represented by an array gain, where each element gain[i] indicates the net change in altitude between two consecutive points: from point i to point i + 1. Your objective is to determine the highest altitude reached during this trip.

Examples

Example 1

Input:

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

Output:

1

Explanation:

The altitudes are [0, -5, -4, 1, 1, -6]. The highest is 1.

Example 2

Input:

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

Output:

0

Explanation:

The altitudes are [0, -4, -7, -9, -10, -6, -3, -1]. The highest is 0.

Constraints

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

Approach and Intuition

The problem requires simulating a biker's altitude changes over a sequence of elevation gains or losses and determining the highest point reached.

  1. Initialize Altitude and Maximum Altitude:

    • Start at altitude 0 and initialize a variable max_altitude to 0.

  2. Simulate the Journey:

    • Iterate through the gain array.
    • At each step, add gain[i] to the current altitude.
    • After each addition, check if the current altitude exceeds max_altitude. If so, update max_altitude.

  3. Return the Result:

    • Once the array is fully traversed, return the highest altitude stored in max_altitude.

This linear simulation leverages the small constraint size (n ≤ 100) and ensures that the maximum is found with minimal overhead.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int maxAltitude(vector<int>& heightChange) {
        int altitude = 0;
        int highest = altitude;
            
        for (int delta : heightChange) {
            altitude += delta;
            highest = max(highest, altitude);
        }
            
        return highest;
    }
};

In the given C++ program, the goal is to find the highest altitude attained given a list of changes in altitude (heightChange). The program defines a class Solution that includes the method maxAltitude, which takes in a vector of integers representing the changes in altitude.

Here's how the program works:

  1. Initialize altitude to 0, which represents the starting altitude.
  2. Also, initialize highest to the same value as altitude. This variable will track the highest altitude reached as the changes are applied.

The method then enters a loop to process each altitude change:

  1. For each value (delta) in the heightChange vector, add delta to altitude. This updates the current altitude based on the change.
  2. Then, update highest to be the maximum of the current highest value or the updated altitude. This ensures highest always holds the maximum altitude reached during the iteration.

Finally, after all altitude changes are processed, the method returns the highest value, representing the maximum altitude achieved during the flight. This approach efficiently computes the highest altitude with a single traversal of the input vector, thus maintaining an O(n) time complexity, where n is the length of the input vector.

java 
class Solution {
  public int maxAltitude(int[] altChanges) {
    int current = 0;
    int maxAltitude = current;
    
    for (int change : altChanges) {
      current += change;
      maxAltitude = Math.max(maxAltitude, current);
    }
    
    return maxAltitude;
  }
}

The given Java solution determines the highest altitude reached, given a sequence of altitude changes. The method maxAltitude takes an array of integers altChanges where each integer represents a change in altitude. It initializes current altitude to zero and sets maxAltitude also to zero. As it iterates over each altitude change in the array, it updates the current altitude by adding the change to the existing altitude. It then compares the updated current altitude with the maxAltitude using the Math.max function, updating maxAltitude to the higher value. Finally, the method returns the highest altitude achieved during the course of travel. This implementation efficiently tracks and updates the peak altitude in a single pass through the altitude changes array.

python 
class Solution:
    def maxAltitude(self, changes: List[int]) -> int:
        current_level = 0
        max_altitude = current_level
    
        for change in changes:
            current_level += change
            max_altitude = max(max_altitude, current_level)
    
        return max_altitude

In the Python program provided to find the highest altitude, you track altitude changes as a list of integers passed to the function maxAltitude. The function uses variables current_level to accumulate these altitude changes and max_altitude to keep track of the highest altitude reached during the journey.

The process unfolds as follows:

  • Initiate current_level at 0, representing the start altitude.
  • Assign the same value to max_altitude as a starting point for the highest altitude.
  • Iterate over each altitude change in the changes list:
    • Increment current_level by the current change value.
    • Update max_altitude if current_level is higher than the current max_altitude.
  • The function concludes by returning the highest altitude attained, stored in max_altitude.

This approach ensures that after processing all altitude changes, you obtain the maximum altitude reached efficiently.

Comments