Find the Highest Altitude

Difficulty: Easy | Acceptance: 83.90% | Paid: No Topics: Array, Prefix Sum

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts at altitude 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.

• Examples
• Constraints
• Approach 1: Iterative Prefix Sum
• Approach 2: Explicit Array Construction
• Approach 3: Functional / Reduce

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 1: Iterative Prefix Sum

Intuition We can simulate the journey by keeping a running sum of the altitude gains. As we calculate the current altitude, we compare it with the maximum altitude found so far.

Steps

• Initialize current_altitude and max_altitude to 0.
• Iterate through the gain array.
• Add the current gain to current_altitude.
• Update max_altitude if current_altitude is greater.
• Return max_altitude.

from typing import List

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        current = 0
        max_altitude = 0
        for g in gain:
            current += g
            max_altitude = max(max_altitude, current)
        return max_altitude

Complexity

• Time: O(n)
• Space: O(1)
• Notes: This is the most optimal approach as it only requires a single pass and constant extra space.

Approach 2: Explicit Array Construction

Intuition We can explicitly construct the array of altitudes visited at each point. The first point is 0, and each subsequent point is the sum of the previous altitude and the corresponding gain. Finally, we find the maximum value in this array.

Steps

• Create an array altitudes of size n + 1 initialized to 0.
• Iterate from 0 to n - 1.
• Set altitudes[i + 1] = altitudes[i] + gain[i].
• Return the maximum value in altitudes.

from typing import List

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        altitudes = [0] * (len(gain) + 1)
        for i in range(len(gain)):
            altitudes[i + 1] = altitudes[i] + gain[i]
        return max(altitudes)

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses O(n) extra space to store the altitude history, which is not necessary since we only need the maximum value.

Approach 3: Functional / Reduce

Intuition We can use a functional programming style (like reduce) to accumulate the current altitude and track the maximum simultaneously in a single expression.

Steps

• Use the reduce function on the gain array.
• The accumulator holds an object or tuple with current altitude and max altitude.
• Update the accumulator for each gain value.
• Return the max value from the final accumulator.

from typing import List
from functools import reduce

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        return reduce(lambda acc, g: (acc[0] + g, max(acc[1], acc[0] + g)), gain, (0, 0))[1]

Complexity

• Time: O(n)
• Space: O(1)
• Notes: While concise, this approach may be less readable to some developers compared to the iterative loop. In Java and C++, the standard loop is preferred over functional streams for this specific stateful accumulation.