1732.Find_the_Highest_Altitude(Easy).md

1732. Find the Highest Altitude (Easy)

Date and Time: Oct 14, 2024, 20:32 (EST)

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

Question:

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.length

• 1 <= n <= 100

• -100 <= gain[i] <= 100

Walk-through:

Use two variables: curSum to keep track of the sum of all prev elements, res to maintain the current maximum altitude.

Python Solution:

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        # two variables: currSum, res
        # currSum is the sum of all prev values
        # res is the current max altitude

        # TC: O(n), SC: O(1)
        curSum, res = 0, 0
        for i in gain:
            curSum += i
            res = max(res, curSum)
        return res

Time Complexity: $O(n)$, n is len(gain).
Space Complexity: $O(1)$