We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Highest Altitude

Number: 1833

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Apple, Adobe

Problem Description

Given an array representing the net gain in altitude between successive points on a biker's route (starting from altitude 0), compute the highest altitude reached during the trip.

Key Insights

  • The altitude at any given point is the cumulative sum (prefix sum) of the gains.
  • The maximum altitude is the highest cumulative sum obtained when iterating through the array.
  • A single pass through the array (O(n) time) is sufficient, while only O(1) extra space is required.

Space and Time Complexity

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

Solution

The approach is to initialize the current altitude to 0 and then iterate over each value in the gains array to update the current altitude. During each iteration, the maximum altitude encountered so far is updated if the current altitude exceeds it. The algorithm uses a simple loop and two variables (one for the current altitude and one for the maximum altitude).

Code Solutions

# Function to find the highest altitude
def largestAltitude(gain):
    current_altitude = 0  # Initialize current altitude to 0 (starting altitude)
    max_altitude = 0      # Initialize max altitude as 0
    # Loop through each net gain in the given array
    for change in gain:
        current_altitude += change  # Update current altitude
        # Update max altitude if current altitude is higher
        if current_altitude > max_altitude:
            max_altitude = current_altitude
    return max_altitude

# Example usage:
print(largestAltitude([-5,1,5,0,-7]))  # Expected output: 1
← Back to All Questions