LeetCode Python/Java/C++/JS  >  1732. Find the Highest Altitude  >  Solved in Python, Java, JavaScript, Cpp, Csharp, Go, Ruby, Rust, Kotlin, Swift  >  GitHub

    LeetCode link: 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.*

    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
    Topics

    Array Prefix Sum

    Hint 1

    Let's note that the altitude of an element is the sum of gains of all the elements behind it

    Hint 2

    Getting the altitudes can be done by getting the prefix sum array of the given array

    Intuition
    PreviousNext

    The problem requires finding the highest altitude reached during a road trip. The biker starts at altitude 0. The gain array represents the change in altitude between consecutive points.

    This implies that the altitude at point i is the sum of all gains up to point i-1.

    We can maintain a running sum (prefix sum) to represent the current altitude and continuously update the maximum altitude encountered so far.

    👋 Hi, I'm the developer behind coder.id — Build your programmer brand. Create your portfolio, resume, and blog in minutes, and land your dream offer!

    Step-by-Step Solution

    1. Initialize two variables: current_altitude to 0 and max_altitude to 0.
    2. Iterate through each value g in the gain array.
    3. Add g to current_altitude to calculate the altitude of the next point.
    4. Update max_altitude with the maximum of max_altitude and current_altitude.
    5. After the loop finishes, return max_altitude.

    Complexity

    Time complexity

    O(N)

    Space complexity

    O(1)

    Explanation

    • Time Complexity: O(N), where N is the length of the array gain. We only need to traverse the array once.
    • Space Complexity: O(1). We only use a few integer variables to store the current and maximum altitudes, so the extra space required is constant.

    Solution in languages: Python Java JavaScript Cpp Csharp Go Ruby Rust Kotlin Swift

    Python # 

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

        for g in gain:
            current_altitude += g
            if current_altitude > max_altitude:
                max_altitude = current_altitude

        return max_altitude

    Java # 

    class Solution {
    public int largestAltitude(int[] gain) {
        int currentAltitude = 0;
        int maxAltitude = 0;

        for (int g : gain) {
            currentAltitude += g;
            if (currentAltitude > maxAltitude) {
                maxAltitude = currentAltitude;
            }
        }

        return maxAltitude;
    }
}

    JavaScript # 

    /**
 * @param {number[]} gain
 * @return {number}
 */
var largestAltitude = function(gain) {
    let currentAltitude = 0;
    let maxAltitude = 0;

    for (const g of gain) {
        currentAltitude += g;
        if (currentAltitude > maxAltitude) {
            maxAltitude = currentAltitude;
        }
    }

    return maxAltitude;
};

    Cpp # 

    class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int currentAltitude = 0;
        int maxAltitude = 0;

        for (int g : gain) {
            currentAltitude += g;
            if (currentAltitude > maxAltitude) {
                maxAltitude = currentAltitude;
            }
        }

        return maxAltitude;
    }
};

    Csharp # 

    public class Solution {
    public int LargestAltitude(int[] gain) {
        int currentAltitude = 0;
        int maxAltitude = 0;

        foreach (int g in gain) {
            currentAltitude += g;
            if (currentAltitude > maxAltitude) {
                maxAltitude = currentAltitude;
            }
        }

        return maxAltitude;
    }
}

    Go # 

    func largestAltitude(gain []int) int {
    currentAltitude := 0
    maxAltitude := 0

    for _, g := range gain {
        currentAltitude += g
        if currentAltitude > maxAltitude {
            maxAltitude = currentAltitude
        }
    }

    return maxAltitude
}

    Ruby # 

    # @param {Integer[]} gain
# @return {Integer}
def largest_altitude(gain)
    current_altitude = 0
    max_altitude = 0

    gain.each do |g|
        current_altitude += g
        max_altitude = current_altitude if current_altitude > max_altitude
    end

    max_altitude
end

    Rust # 

    impl Solution {
    pub fn largest_altitude(gain: Vec<i32>) -> i32 {
        let mut current_altitude = 0;
        let mut max_altitude = 0;

        for g in gain {
            current_altitude += g;
            if current_altitude > max_altitude {
                max_altitude = current_altitude;
            }
        }

        max_altitude
    }
}

    Kotlin # 

    class Solution {
    fun largestAltitude(gain: IntArray): Int {
        var currentAltitude = 0
        var maxAltitude = 0

        for (g in gain) {
            currentAltitude += g
            if (currentAltitude > maxAltitude) {
                maxAltitude = currentAltitude
            }
        }

        return maxAltitude
    }
}

    Swift # 

    class Solution {
    func largestAltitude(_ gain: [Int]) -> Int {
        var currentAltitude = 0
        var maxAltitude = 0

        for g in gain {
            currentAltitude += g
            if currentAltitude > maxAltitude {
                maxAltitude = currentAltitude
            }
        }

        return maxAltitude
    }
}
    Solution in languages: Python Java JavaScript Cpp Csharp Go Ruby Rust Kotlin Swift

    Other languages

    Welcome to contribute code to GitHub repo -> 1732. Find the Highest Altitude. Thanks!
    PreviousNext

    Level Up Your Developer Identity

    • 📄 Resume, Portfolio & Blog
    • 🌐 Custom Domain Binding Supported
    • ✨ Premium Subdomain: https://yourname.coder.id

    Build Your Developer Brand at coder.id →