Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Find the Highest Altitude (easy)

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

Problem Statement

A bike rider is going on a ride. The road contains n + 1 points at different altitudes. The rider starts from point 0 at an altitude of 0.

Given an array of integers gain of length n, where gain[i] represents the net gain in altitude between points i and i + 1 for all (0 <= i < n), return the highest altitude of a point.

Examples

Example 1

  • Input: gain = [-5, 1, 5, 0, -7]
  • Expected Output: 1
  • Justification: The resulting altitudes are [-5, -4, 1, 1, -6], where 1 is the highest altitude reached.

Example 2

  • Input: gain = [4, -3, 2, -1, -2]
  • Expected Output: 4
  • Justification: The resulting altitudes are [4, 1, 3, 2, 0], where 4 is the highest altitude reached.

Example 3

  • Input: gain = [2, 2, -3, -1, 2, 1, -5]
  • Expected Output: 4
  • Justification: The resulting altitudes are [2, 4, 1, 0, 2, 3, -2], where 4 is the highest altitude reached.

Constraints:

  • n == gain.length
  • 1 <= n <= 100
  • -100 <= gain[i] <= 100

Solution

The question does not give you altitudes. It gives you the change between one point and the next. So the first job is turning those changes back into altitudes.

The rider starts at point 0 at altitude 0. Adding gain[0] gives the altitude at point 1. Adding gain[1] to that gives the altitude at point 2, and so on. This is a running total, the same prefix sum idea as the running sum question earlier in the chapter.

You do not have to store those altitudes. You only need the largest one. So carry two numbers as you walk: the altitude you are at now, and the highest altitude you have seen so far.

Both start at 0, and that 0 is a real value, not a placeholder. The rider is standing at altitude 0 before the first leg, so 0 is already a valid answer. This is why an input where every gain is negative still answers 0. The rider only goes down, so the starting point was the highest point of the trip.

Image

Step-by-step Algorithm

  1. Set currentAltitude to 0 and maxAltitude to 0. Both describe point 0, where the rider starts.
  2. For each value in gain:
    • Add it to currentAltitude. That value can be positive, negative or zero.
    • If currentAltitude is now larger than maxAltitude, set maxAltitude to it.
  3. When the list is finished, return maxAltitude.

One pass, two numbers, and no array is ever built. The altitudes exist only one at a time, which is all the question needs.

Algorithm Walkthrough

mediaLink

The altitude moves by -5 to -5, and the best stays 0

1 of 6

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Single pass: The algorithm iterates through the gain array once, processing each element to update the currentAltitude and check the maxAltitude. This requires O(N) time, where N is the length of the gain array.

  • No nested loops or repeated operations are present, so the time complexity remains linear.

Overall time complexity: O(N).

Space Complexity

  • Constant space: The algorithm only uses a few extra variables (currentAltitude and maxAltitude), both of which require constant space, O(1).

  • No additional data structures (like arrays or lists) are used that scale with the input size.

Overall space complexity: O(1).

Wasiu Yusuf

Wasiu Yusuf

· a month ago

0(N) time complexity and 0(1) time complexity.



class Solution:
    def largestAltitude(self, gain):
        max_altitude = 0  # To store the maximum altitude encountered
        # TODO: Write your code here

        all_sum = 0
        for i in range(len(gain)):
            all_sum += gain[i]
            max_altitude = max(max_altitude, all_sum)

        return max_altitude
Show 1 reply
A

anusha.inapakolla94

· 3 years ago

Hi Team,

May I know how many testcases each problem will be having as I could see 65 testcases are passed for one problem and 50 for another.

Show 1 reply
T

tranlannhi

· 3 years ago

Would the solution with time O(logn) be better than O(n)? Could you please provide input for the following solution?

class Solution {
    largestAltitude(gain) {
        let maxAltitude = 0;  
        let altChange = new Array(gain.length)
        altChange[0] = gain[0]
        for (let i=1; i< gain.length; i++){
          altChange[i] = gain[i] + altChange[i-1]
        }
        altChange.sort((a,b) => b-a)
        maxAltitude = altChange[0]
        return maxAltitude;
    }
}
Show 4 replies
C

cednice

· 3 years ago

If altitude array values are all negative, then initializing maxAltitude to zero will produce the incorrect answer.

Show 3 replies

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity