Leetcode 1732. Find the Highest Altitude
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 his trip at point 0 with an altitude of 0. We 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). We need to find and return the highest altitude of a point.
Example
Let's say we have an input array gain = [-5, 1, 5, 0, -7]
. We need to find the highest altitude the biker reaches.
- The biker starts at altitude 0. So the altitudes array begins with [0].
- The first gain in altitude is -5, so the biker goes to altitude 0 + (-5) = -5. Now the altitudes array is [0, -5].
- The next gain in altitude is 1, adding to the previous altitude gives us -5 + 1 = -4. So, the altitudes array becomes [0, -5, -4].
- Following the same process, we update the altitudes array: [0, -5, -4, 1, 1, -6].
- After updating the altitudes array, we find the highest altitude in the array, which is 1.
The output for this example is 1.
Approach
We can solve this problem using a single pass through the gain
array.
- Initialize a variable
highest_altitude
to store the highest altitude found, initially set to 0. - Initialize a variable
current_altitude
to store the current altitude of the biker, initially set to 0. - Iterate through the
gain
array and for each element: a. Add the gain to thecurrent_altitude
b. Compare thecurrent_altitude
withhighest_altitude
. - Ifcurrent_altitude
is greater thanhighest_altitude
, updatehighest_altitude
withcurrent_altitude
. - Return
highest_altitude
after the loop finishes.
Python Solution
1class Solution:
2 def largestAltitude(self, gain: List[int]) -> int:
3 highest_altitude = current_altitude = 0
4 for g in gain:
5 current_altitude += g
6 highest_altitude = max(highest_altitude, current_altitude)
7 return highest_altitude
Java Solution
1class Solution {
2 public int largestAltitude(int[] gain) {
3 int highestAltitude = 0;
4 int currentAltitude = 0;
5 for (int g : gain) {
6 currentAltitude += g;
7 highestAltitude = Math.max(highestAltitude, currentAltitude);
8 }
9 return highestAltitude;
10 }
11}
JavaScript Solution
1class Solution {
2 largestAltitude(gain) {
3 let highestAltitude = 0;
4 let currentAltitude = 0;
5 for (let g of gain) {
6 currentAltitude += g;
7 highestAltitude = Math.max(highestAltitude, currentAltitude);
8 }
9 return highestAltitude;
10 }
11}
C++ Solution
1class Solution {
2public:
3 int largestAltitude(vector<int>& gain) {
4 int highestAltitude = 0;
5 int currentAltitude = 0;
6 for (int g : gain) {
7 currentAltitude += g;
8 highestAltitude = max(highestAltitude, currentAltitude);
9 }
10 return highestAltitude;
11 }
12};
C# Solution
1public class Solution {
2 public int LargestAltitude(int[] gain) {
3 int highestAltitude = 0;
4 int currentAltitude = 0;
5 foreach (int g in gain) {
6 currentAltitude += g;
7 highestAltitude = Math.Max(highestAltitude, currentAltitude);
8 }
9 return highestAltitude;
10 }
11}
Conclusion
We have provided working solutions in Python, Java, JavaScript, C++, and C# for this problem. Using a single pass through the gain
array, these solutions calculate the highest and current altitudes by iterating through the array, adding each gain, comparing it with the previous maximum altitude, and returning the highest altitude reached.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.