Find the Highest Altitude

EASY

Description

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

Approaches

Checkout 2 different approaches to solve Find the Highest Altitude. Click on different approaches to view the approach and algorithm in detail.

Two-Pass Approach: Store All Altitudes

This approach first calculates all the altitudes reached during the trip and stores them in a separate array. After computing all altitudes, it then iterates through this new array to find the maximum value.

Algorithm

Create a new integer array altitudes of size n + 1 to store the altitude at each point.
Initialize the starting altitude: altitudes[0] = 0.
Iterate through the gain array from i = 0 to n - 1.
In each iteration, calculate the next altitude: altitudes[i + 1] = altitudes[i] + gain[i].
After populating the altitudes array, initialize a variable maxAltitude to the first altitude, altitudes[0].
Iterate through the altitudes array and update maxAltitude with the maximum value found.
Return maxAltitude.

The core idea is to simulate the entire trip by first computing the altitude at every point. We know the trip starts at altitude 0. The altitude at point i+1 is simply the altitude at point i plus the gain gain[i]. We can use an auxiliary array, say altitudes, of size n+1 to store these values. Once this array is fully populated, a second pass is made through it to find the maximum value, which is the answer.

class Solution {
    public int largestAltitude(int[] gain) {
        int n = gain.length;
        int[] altitudes = new int[n + 1];
        altitudes[0] = 0;

        // First pass: calculate all altitudes
        for (int i = 0; i < n; i++) {
            altitudes[i + 1] = altitudes[i] + gain[i];
        }

        // Second pass: find the maximum altitude
        int maxAltitude = altitudes[0];
        for (int i = 1; i <= n; i++) {
            if (altitudes[i] > maxAltitude) {
                maxAltitude = altitudes[i];
            }
        }
        
        return maxAltitude;
    }
}

Complexity Analysis

Time Complexity: O(n), where n is the length of the `gain` array. We perform two separate loops, each running up to n times, resulting in O(n) + O(n) = O(n) time.Space Complexity: O(n), to store the `altitudes` array of size `n + 1`.

Pros and Cons

Pros:

Conceptually simple and easy to follow.
Separates the logic of calculating altitudes from finding the maximum, which can make the code easier to read and debug.

Cons:

Requires extra space proportional to the number of points, which is inefficient compared to a constant space solution.

Code Solutions

Checking out 4 solutions in different languages for Find the Highest Altitude. Click on different languages to view the code.

/** * @param {number[]} gain * @return {number} */ var largestAltitude =
  function (gain) {
    let ans = 0;
    let h = 0;
    for (const v of gain) {
      h += v;
      ans = Math.max(ans, h);
    }
    return ans;
  };

Video Solution

Watch the video walkthrough for Find the Highest Altitude

Patterns:

Prefix Sum

Data Structures:

Array