Find the Highest Altitude
EasyPrompt
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.length1 <= 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
- Create a new integer array
altitudesof sizen + 1to store the altitude at each point. - Initialize the starting altitude:
altitudes[0] = 0. - Iterate through the
gainarray fromi = 0ton - 1. - In each iteration, calculate the next altitude:
altitudes[i + 1] = altitudes[i] + gain[i]. - After populating the
altitudesarray, initialize a variablemaxAltitudeto the first altitude,altitudes[0]. - Iterate through the
altitudesarray and updatemaxAltitudewith the maximum value found. - 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.
This is the most optimal approach. Instead of storing all the altitudes, we can calculate them one by one and keep track of the maximum altitude found so far in a single pass. This avoids the need for an extra array.
Algorithm
- Initialize a variable
currentAltitudeto 0, representing the altitude at the current point. - Initialize a variable
maxAltitudeto 0, as this is the starting altitude and the initial highest point. - Iterate through the
gainarray. - For each
gingain, update the current altitude:currentAltitude += g. - Compare the
currentAltitudewithmaxAltitudeand updatemaxAltitudeif the current one is higher:maxAltitude = Math.max(maxAltitude, currentAltitude). - After the loop finishes,
maxAltitudewill hold the highest altitude reached during the trip. ReturnmaxAltitude.
Walkthrough
We can optimize the previous approach by realizing that we don't need to store all the altitudes. We only need to know the current altitude to calculate the next one, and we only need to keep track of the highest altitude seen so far. We can use two variables: currentAltitude to track the altitude as we iterate, and maxAltitude to store the maximum value found. Both are initialized to 0, the starting altitude. We then iterate through the gain array, updating the currentAltitude and comparing it with maxAltitude at each step. This eliminates the need for extra storage and a second pass.
class Solution { public int largestAltitude(int[] gain) { int currentAltitude = 0; // The highest altitude starts at 0, the initial altitude. int maxAltitude = 0; for (int g : gain) { currentAltitude += g; maxAltitude = Math.max(maxAltitude, currentAltitude); } return maxAltitude; }}Complexity
Time
O(n), where n is the length of the `gain` array. We iterate through the array only once.
Space
O(1), as we only use a few variables to store the current and maximum altitudes, regardless of the input size.
Trade-offs
Pros
Highly efficient, using only constant extra space.
Solves the problem in a single iteration through the input array.
Cons
Combines the calculation and comparison steps, which might be slightly less intuitive for beginners than the two-pass method.
Solutions
Solution
/** * @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; };class Solution { public int largestAltitude ( int [] gain ) { int ans = 0 , h = 0 ; for ( int v : gain ) { h += v ; ans = Math . max ( ans , h ); } return ans ; } }class Solution { public: int largestAltitude ( vector < int >& gain ) { int ans = 0 , h = 0 ; for ( int v : gain ) h += v , ans = max ( ans , h ); return ans ; } };class Solution : def largestAltitude ( self , gain : List [ int ]) -> int : return max ( accumulate ( gain , initial = 0 ))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.