Scale Engineer

Find the Highest Altitude

Easy
#1586Time: 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: O(n), to store the `altitudes` array of size `n + 1`.
Patterns
Prefix Sum
Data structures
Array

Prompt

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

2 approaches with complexity analysis and trade-offs.

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

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

Walkthrough

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

Time

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

O(n), to store the `altitudes` array of size `n + 1`.

Trade-offs

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.

Solutions

/** * @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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem