Solving Leetcode 1732. Find the Highest Altitude

As rains from Tropical Storm Henri give the city streets knee-deep with water, delays throughout the subway, and the ever-present flash flood warning, let’s take a minute, take a breath and stroll through this easy Leetcode, as we find the highest altitude.

https://unsplash.com/photos/ByUAo3RpA6c

The problem reads…

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.

Constraints:

n == gain.length

1 <= n <= 100

-100 <= gain[i] <= 100

The examples give us a hint for one possible route to take to solve this algorithm, we could build a new array, starting at 0, and push the mathematical altitude changes, then take the max of the array. That’s one way, but I’m going to go a different way.

Instead of creating a new array and tracking all the numbers I’ll start by declaring two variables, one will hold the path as we travel through the array, and the other will hold the current highest altitude, so we can compare the path to the previous highest as we go.

First though, I’ll do a walkthrough of what I think the loop should look like. I do this often when I’m determining what needs to be included and to help find any potential snags or edge cases.

I like to manually step through a loop before I jump into code sometimes, to ensure that what I see in my mind will work out when I start coding it.

As we can see, with two variables declared at 0 when we start, we go through the array and add gain[i] to path and then immediately compare path to highest. If path is greater than highest, then we reassign highest to equal path, the current largest altitude gain.

Once we reach the end of our loop we just have to return highest, and we’re done! So let’s go ahead and turn this step through into actual JavaScript.

So first we can go ahead and declare the variables, and may as well throw in our return.

Next we build out our for loop and take care of our first step, and that’s adding each index of gain to our existing path. Lastly we’ll want to compare path to highest, and reassign if highest to equal path if path is greater than highest.

And there we have it. Leetcode’s easy algorithm number 1732! Thanks for reading and if you have any algorithm, or software engineering bootcamp questions drop ’em in the comments!