1732. Find the Highest Altitude

Problem Description

The problem presents a scenario where a biker is going on a road trip across n + 1 points that are situated at varying altitudes. He begins his journey from point 0, which is at sea level (altitude 0). The altitude changes as he moves from one point to the next, and these changes are represented by an array named gain, where each element gain[i] indicates the net altitude gain (or loss, if the value is negative) as the biker moves from point i to point i + 1. The objective is to figure out what the highest altitude the biker reaches during his trip is. The length of the gain array is n, with i ranging from 0 to n - 1.

Intuition

To solve this problem, we need to keep track of the biker's altitude as he moves from one point to the next. We start at an altitude of 0 and add the net gain from the gain array consecutively to find the altitude at each subsequent point. While doing this, we keep an eye on the highest altitude reached thus far.

The solution approach involves two main steps:

Initialize a variable to keep track of the biker's altitude as he progresses on the trip (h in the given solution).
Initialize another variable to maintain the highest altitude (ans in the given solution) seen so far.

In a loop, we add each net gain to the current altitude h. After each addition, we compare the new altitude h with the current highest altitude ans. If h is greater than ans, it means we have found a new highest altitude, and we update ans to reflect this new value. We continue this process for all points to ensure we find the absolute highest altitude reached. Ultimately, we return the value of ans as the solution, which represents the highest altitude reached during the trip.

Learn more about Prefix Sum patterns.

Solution Approach

The given solution is a straightforward iterative approach. In terms of algorithms, data structures, or patterns used, this solution is very simple and doesn't employ complex data structures or algorithms. Here’s a step-by-step walk-through of the implementation:

First, we define a function largestAltitude that takes an List[int] named gain as input.
Within the function, we initialize two variables, ans and h, to 0. Variable ans is used to keep track of the highest altitude reached, while h keeps track of the current altitude.
We iterate over each value v in the gain array using a for loop.
On each iteration, we increment the current altitude h by the net gain value v. This represents the altitude at the current point i + 1.
Next, we use the max function to update the ans. The max function takes two arguments, the current highest altitude ans and the new altitude h. If h is higher, ans is updated to h, otherwise it remains the same.
After the loop completes, all points have been visited, and the ans contains the highest altitude the biker reaches.
Finally, the function returns the value stored in ans.

To summarize, the solution iterates once through the list of altitude gains, keeps a running sum, and simultaneously tracks the maximum altitude encountered. No complex data structures are used, and the time complexity is O(n), where n is the size of the gain list, as it requires a single traversal of the list.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach with a gain array of [4,-1,3,1,-5]. This array represents the net altitude gain or loss as the biker moves from one point to another.

We start by initializing the current altitude, h, to 0, since the biker starts his journey at sea level. Likewise, we initialize the highest altitude reached, ans, also to 0.

Walkthrough of the steps:

The first element in gain is 4, the biker moves from point 0 to point 1 and gains 4 units of altitude. The new current altitude h becomes 4. Since 4 > 0, we update ans to be 4.
The next element is -1, representing a loss of altitude as the biker moves to the next point. Adjusting the current altitude h by -1, we get h = 4 - 1 = 3. The highest altitude ans remains 4, as 3 is not greater than 4.
The biker gains 3 units of altitude at the next step, which makes the new h = 3 + 3 = 6. This is greater than our current highest altitude ans, so we update ans to 6.
Another gain is encountered, 1 unit, thus h = 6 + 1 = 7. Again, this is higher than the previous 'ans', so ans is updated to 7.
The last element is -5, when the biker moves to the final point, losing 5 units. So h becomes 7 - 5 = 2. Since 2 is not greater than the current ans which is 7, we make no changes to ans.

After iterating through the entire gain array, we've kept track of the current and highest altitudes at each point. The final value of ans is 7, which means the highest altitude reached by the biker during his trip is 7 units above sea level.

Finally, we return 7 as our answer.

Solution Implementation

1from typing import List  # Import List from typing module to use for type hinting
2
3class Solution:
4    def largest_altitude(self, gain: List[int]) -> int:
5        # Initialize variables:
6        # max_altitude to track the highest altitude reached
7        # current_altitude to keep the running sum of altitude changes
8        max_altitude, current_altitude = 0, 0
9      
10        # Iterate through each altitude change in the list
11        for altitude_change in gain:
12            # Add the altitude change to the current altitude
13            current_altitude += altitude_change
14          
15            # Update max_altitude if the current altitude is higher
16            max_altitude = max(max_altitude, current_altitude)
17      
18        # Return the maximum altitude reached
19        return max_altitude
20

1class Solution {
2    public int largestAltitude(int[] gain) {
3        int maxAltitude = 0;   // Variable to store the highest altitude reached
4        int currentAltitude = 0; // Variable to track the current altitude
5      
6        // Loop through all the altitude gains
7        for (int altitudeGain : gain) {
8            // Update the current altitude by adding the altitude gain
9            currentAltitude += altitudeGain;
10            // Update maxAltitude if the currentAltitude is greater than the maxAltitude seen so far
11            maxAltitude = Math.max(maxAltitude, currentAltitude);
12        }
13      
14        // Return the highest altitude reached
15        return maxAltitude;
16    }
17}
18

1#include <vector>
2#include <algorithm> // Include for the max() function
3
4class Solution {
5public:
6    // This function calculates the largest altitude reached
7    // based on changes in altitude represented by the 'gain' vector.
8    int largestAltitude(vector<int>& gain) {
9        int largestAltitudeReached = 0; // Will store the maximum altitude reached
10        int currentAltitude = 0; // Will keep track of the current altitude
11
12        // Iterate through each gain value
13        for (int altitudeChange : gain) {
14            currentAltitude += altitudeChange; // Update the current altitude by adding the altitude change
15            largestAltitudeReached = max(largestAltitudeReached, currentAltitude); // Update maximum altitude if current altitude is higher
16        }
17      
18        // Return the highest altitude reached during the hike
19        return largestAltitudeReached;
20    }
21};
22

1/**
2 * This function calculates the highest altitude reached in a journey given the gain in altitude at each step.
3 * @param {number[]} altitudeGain - An array of numbers representing the altitude gain at each step of the journey.
4 * @return {number} - The highest altitude reached during the journey.
5 */
6const largestAltitude = (altitudeGain: number[]): number => {
7    let highestAltitude: number = 0; // Initialize the highest altitude
8    let currentAltitude: number = 0; // Initialize the current altitude
9
10    // Loop through the altitude gain at each step
11    for (const altitudeChange of altitudeGain) {
12        currentAltitude += altitudeChange; // Update the current altitude
13        highestAltitude = Math.max(highestAltitude, currentAltitude); // Update the highest altitude if current is greater
14    }
15
16    return highestAltitude; // Return the highest altitude reached
17};
18

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the length of the gain list. This is because the code iterates through each element of the gain list exactly once.

Space Complexity

The space complexity of the given code is O(1) (constant space complexity). This is because the space used does not grow with the size of the input; only a fixed amount of extra space is used for variables ans and h regardless of input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know