algoadvance

Leetcode 1732. Find the Highest Altitude

Problem Statement

A cyclist rides a bike on a road that follows a sequence of points with varying altitudes. You are given an array gain where gain[i] is the net gain (or loss) in altitude between point i and point i + 1 for all i (0 ≤ i < gain.length). The initial altitude is 0, and you need to return the highest altitude the cyclist reaches.

Clarifying Questions

  1. Can altitude values be negative?
    • Yes, gain values can be negative, indicating a loss in altitude.
  2. What should be the return value if there are no gain values?
    • If gain is empty, the starting altitude (which is 0) is the highest altitude.
  3. Are there any constraints on the size of the input array?
    • The constraints would typically align with typical LeetCode constraint guidelines — array size could be up to (10^4), and individual gain values could range between -100 and 100.

Strategy

  1. Initialize the current altitude to be 0.
  2. Traverse through the gain array, updating the current altitude at each step by adding the net gain (or subtracting if it’s a loss).
  3. Keep track of the highest altitude encountered during the traversal.
  4. Return the highest altitude recorded.

Time Complexity

Code

#include <vector>
#include <algorithm> // for max

int largestAltitude(std::vector<int>& gain) {
    int current_altitude = 0;
    int highest_altitude = 0;
    
    for (int g : gain) {
        current_altitude += g;
        highest_altitude = std::max(highest_altitude, current_altitude);
    }
    
    return highest_altitude;
}

Here’s a brief description of the code:

  1. Initialization: Start from 0 altitude (current_altitude) and initialize highest_altitude to 0.
  2. Loop through each gain entry: Update the current_altitude by adding the current gain value. Use std::max to update highest_altitude if current_altitude is higher.
  3. Return the highest altitude achieved.

This solution ensures we efficiently track the highest altitude without needing additional space beyond a few integer variables.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI