Leetcode – Find the Highest Altitude Solution

One of the problems available on Leetcode is the “Find the Highest Altitude” problem. This problem is relatively straightforward and serves as a good exercise for understanding array manipulation techniques in Python. This article aims to provide an in-depth look at how to solve this problem effectively.

Problem Statement

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts at point 0 with altitude equal 0, then climbs up or down to a point 1 with altitude change gain[0], then climbs up or down to a point 2 with altitude change gain[1], and so on until point n with altitude change gain[n – 1].

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.

Brute-Force Approach

Let’s first look at a brute-force solution.

Python Code:

def largestAltitude(gain):
    highest_altitude = 0
    current_altitude = 0
    
    for g in gain:
        current_altitude += g
        highest_altitude = max(highest_altitude, current_altitude)
        
    return highest_altitude

Analysis

The brute-force approach is relatively straightforward. We start at altitude 0 and iterate through the gain array, adding each element to the current altitude. Then, we check if the new altitude is higher than the highest altitude we’ve seen so far. If it is, we update the highest altitude. Finally, we return the highest altitude we’ve reached. The time complexity for this solution is O(n), and the space complexity is O(1).

Optimized Approach

In this case, the brute-force approach is already quite efficient. Nevertheless, we could encapsulate some of the logic into helper functions to make the code more modular and easier to understand.

Python Code:

def update_altitude(current_altitude, gain):
    return current_altitude + gain

def largestAltitude(gain):
    highest_altitude = 0
    current_altitude = 0
    
    for g in gain:
        current_altitude = update_altitude(current_altitude, g)
        highest_altitude = max(highest_altitude, current_altitude)
        
    return highest_altitude

Analysis

This optimized approach doesn’t change the time or space complexities, but it does make the code slightly more readable by encapsulating the logic for updating the altitude into its own function.

Using Built-In Functions

Python has some built-in functions that can make our code even more concise. Specifically, we can use itertools.accumulate to compute the accumulated sums.

Python Code:

import itertools

def largestAltitude(gain):
    return max(0, max(itertools.accumulate(gain)))

Analysis

The time complexity remains O(n), and the space complexity is O(1), not considering the space needed by itertools.accumulate.

Testing

It’s important to test the function to make sure it works as expected.

assert largestAltitude([-5, 1, 5, 0, -7]) == 1
assert largestAltitude([-4, -3, -2, -1, 4, 3, 2]) == 0
assert largestAltitude([1, 2, 3, 4, 5, 6, 7, 8]) == 36

Conclusion

The “Find the Highest Altitude” problem on Leetcode is a great exercise in array manipulation and basic algorithm design. While the problem itself is not very complex, it allows for various approaches that offer good learning experiences in Python programming. Whether you’re new to coding or just looking for some practice, this problem provides a nice challenge.