LC 1732. Find the Highest Altitude (Easy)

🔗: https://leetcode.com/problems/find-the-highest-altitude/

Problem Statement

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 at point 0 with altitude:

0

We are given an array:

gain[]

where each value represents the net gain or loss in altitude between two consecutive points.

We have to return the highest altitude reached during the entire trip.

This was probably one of the easiest questions I have solved till now 😭.

And ngl, this was also the first time I actually solved the Problem of the Day on LeetCode because usually I don't solve it.

Looking at the examples, I was able to understand pretty quickly what the question was asking.

We are given an array called:

gain[]

and it stores the change in altitude between two consecutive points.

The biker starts from:

Altitude = 0

and we need to find the highest altitude reached during the whole journey.

The thing is, to find the highest altitude, first I need to know what the altitudes actually are.

And to know the altitudes, I simply need to keep adding the changes given in the array.

For example:

gain = [-5,1,5,0,-7]

The biker starts at:

Altitude = 0

Now we keep adding the change in altitude at every step.

First gain:

-5

Current altitude becomes:

0 + (-5) = -5

Second gain:

1

Current altitude becomes:

-5 + 1 = -4

Third gain:

5

Current altitude becomes:

-4 + 5 = 1

Fourth gain:

0

Current altitude becomes:

1 + 0 = 1

Fifth gain:

-7

Current altitude becomes:

1 - 7 = -6

So the altitudes during the journey become:

[0,-5,-4,1,1,-6]

And now the question becomes very simple.

We just need to find the highest value among these altitudes.

Here the highest altitude is:

1

which is our answer.

So the approach felt pretty obvious from the question itself.

I don't need any extra array to store all the altitudes because the question is only asking for the highest altitude.

So I made:

alt

to store the current altitude.

And:

maxAlt

to store the maximum altitude seen so far.

Then while traversing the array, I keep updating the current altitude and comparing it with the maximum altitude.

If the current altitude becomes greater, I update the answer.

That's pretty much the entire question 😭.

The important things I noticed were:

1. The gain array does not store altitudes.

2. It stores the change in altitude between consecutive points.

3. The biker always starts from altitude 0.

4. To know the altitude at any point, we keep adding the gains.

5. We only need the highest altitude, not all the altitudes.

6. There is no need for any extra array.

Time Complexity:

O(n)

because we traverse the array once.

Space Complexity:

O(1)

because we only use a couple of variables.

This was my code:

class Solution {
    public int largestAltitude(int[] gain) {
        int n = gain.length;
        int alt = 0;
        int maxAlt = 0;

        for(int i = 0; i < n; i++) {
            alt += gain[i];
            maxAlt = Math.max(alt, maxAlt);
        }

        return maxAlt;
    }
}

This one was pretty straightforward, and honestly it felt great seeing that coin after solving it and getting the answer accepted.

I'll try to solve the Problem of the Day questions on LeetCode more consistently as well.

Any suggestions, corrections, or feedback would be appreciated.

Thanks for reading!!