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.
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, then climbs up or down to a point 2 with altitude change gain, 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.
Let’s first look at a brute-force solution.
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
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).
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.
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
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.
import itertools def largestAltitude(gain): return max(0, max(itertools.accumulate(gain)))
The time complexity remains O(n), and the space complexity is O(1), not considering the space needed by
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
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.