Skip to content

Latest commit

 

History

History
73 lines (47 loc) · 2.59 KB

191.md

File metadata and controls

73 lines (47 loc) · 2.59 KB

1732. Find the Highest Altitude

Difficulty: 🟢 Easy

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.

Examples:

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

Solutions

O(n) solution

Python 3

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        current = 0
        largest = 0
        for net_gain in gain:
            current += net_gain
            largest = max(largest, current)
        return largest

The given solution provides a simple approach to find the highest altitude during the trip.

Here is a step-by-step overview of the solution:

  1. Initialize two variables: current and largest, both set to 0. These variables will keep track of the current altitude and the highest altitude reached, respectively.
  2. Iterate through the gain array, which represents the net gain in altitude between consecutive points.
  3. For each net gain in altitude, update the current altitude by adding the net gain.
  4. Update the largest altitude if the current altitude is greater than the largest altitude seen so far.
  5. Return the largest altitude, which is the highest altitude during the trip.

Complexity Analysis

The time complexity for this solution is O(n), where n is the length of the gain array. We iterate through the array once.

The space complexity is O(1) because we are using a constant amount of additional space to store variables.

Summary

The given solution provides a straightforward approach to find the highest altitude reached during a road trip, given the net gain in altitude between consecutive points. It maintains two variables: current to track the current altitude and largest to track the highest altitude seen so far. The solution runs in linear time and constant space complexity.

NB: If you want to get community points please suggest solutions in other languages as merge requests.