Problem Statement in English

You’re given an integer array gain where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < gain.length). The biker starts at an altitude of 0 on point 0. Return the highest altitude of a point.

Approach

You can solve this problem by iterating through the gain array and keeping track of the current altitude at each point. You also need to keep track of the maximum altitude encountered during the iteration.

And you’re done!

Solution in Python


class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        c = res = 0

        for g in gain:
            c += g
            res = max(res, c)

        return res

Complexity

  • Time: $O(n)$
    Since we are iterating through the gain list once, the time complexity is O(n), where n is the length of the gain list.

  • Space: $O(1)$
    Since we are using only a constant amount of space to store the current altitude and the result, the space complexity is $O(1)$.

And we are done.