Problem

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:

1
2
3
4
5

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:

1
2
3
4
5

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.

Solution

Method 1 – Prefix Sum Traversal

Intuition

The key idea is to track the altitude at each point by accumulating the gains. Since the biker starts at altitude 0, we can compute each subsequent altitude by adding the gain to the previous altitude. The highest altitude is simply the maximum value encountered during this process.

Approach

  1. Initialize the starting altitude to 0 and the answer to 0.
  2. Iterate through the gain array:
    • For each gain, add it to the current altitude.
    • Update the answer if the current altitude is higher than the previous answer.
  3. Return the answer after processing all gains.
  4. Edge case: If all gains are negative, the answer remains 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int ans = 0, alt = 0;
        for (int g : gain) {
            alt += g;
            ans = max(ans, alt);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func largestAltitude(gain []int) int {
    ans, alt := 0, 0
    for _, g := range gain {
        alt += g
        if alt > ans {
            ans = alt
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int largestAltitude(int[] gain) {
        int ans = 0, alt = 0;
        for (int g : gain) {
            alt += g;
            ans = Math.max(ans, alt);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun largestAltitude(gain: IntArray): Int {
        var ans = 0
        var alt = 0
        for (g in gain) {
            alt += g
            ans = maxOf(ans, alt)
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def largestAltitude(self, gain: list[int]) -> int:
        ans: int = 0
        alt: int = 0
        for g in gain:
            alt += g
            ans = max(ans, alt)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn largest_altitude(gain: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut alt = 0;
        for g in gain {
            alt += g;
            ans = ans.max(alt);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    largestAltitude(gain: number[]): number {
        let ans = 0, alt = 0;
        for (const g of gain) {
            alt += g;
            ans = Math.max(ans, alt);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We iterate through the gain array once, where n is the number of gains.
  • 🧺 Space complexity: O(1) — Only a few variables are used for tracking the answer and current altitude.