1732. Find the Highest Altitude Easy

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i​​​​​​ and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

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.

Approach

Input: An integer array gain

Output: Return the highest altitude reached

This problem belongs to the 1D Prefix Sum category.

Starting from i = 0, we iterate through gain, continuously accumulating the current altitude.

We use an ans (or highest) variable to record the maximum altitude seen during the traversal.

Note that the initial altitude of 0 is also included in the comparison.

Implementation

python

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        # Initialize maximum altitude and current altitude to 0
        maxAltitude = 0
        currAltitude = 0

        # Iterate over the gain array, calculating the current altitude and max altitude at each step
        for g in gain:
            # Current altitude is the cumulative sum of step height changes
            currAltitude += g
            # Update the maximum altitude
            maxAltitude = max(maxAltitude, currAltitude)
        
        # Return the maximum altitude
        return maxAltitude

javascript

var largestAltitude = function(gain) {
    let highest = 0;
    let currHeight = 0;

    for (let g of gain) {
        currHeight += g;

        highest = Math.max(highest, currHeight);
    }

    return highest;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

1732. Find the Highest Altitude (English)1732. 找到最高海拔 (Chinese)