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.

1. The biker starts at altitude 0. So the altitudes array begins with [0].
2. The first gain in altitude is -5, so the biker goes to altitude 0 + (-5) = -5. Now the altitudes array is [0, -5].
3. 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].
4. Following the same process, we update the altitudes array: [0, -5, -4, 1, 1, -6].
5. 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.

1. Initialize a variable highest_altitude to store the highest altitude found, initially set to 0.
2. Initialize a variable current_altitude to store the current altitude of the biker, initially set to 0.
3. Iterate through the gain array and for each element: a. Add the gain to the current_altitude b. Compare the current_altitude with highest_altitude. - If current_altitude is greater than highest_altitude, update highest_altitude with current_altitude.
4. 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.