# Find the Highest Altitude
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-highest-altitude)
Canonical: https://scaleengineer.com/dsa/problems/find-the-highest-altitude
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## 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._

**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`

# Approaches
## Two-Pass Approach: Store All Altitudes
This approach first calculates all the altitudes reached during the trip and stores them in a separate array. After computing all altitudes, it then iterates through this new array to find the maximum value.
**Time:** O(n), where n is the length of the `gain` array. We perform two separate loops, each running up to n times, resulting in O(n) + O(n) = O(n) time. · **Space:** O(n), to store the `altitudes` array of size `n + 1`.
**Pros:** Conceptually simple and easy to follow.; Separates the logic of calculating altitudes from finding the maximum, which can make the code easier to read and debug.
**Cons:** Requires extra space proportional to the number of points, which is inefficient compared to a constant space solution.
### Explanation
The core idea is to simulate the entire trip by first computing the altitude at every point. We know the trip starts at altitude 0. The altitude at point `i+1` is simply the altitude at point `i` plus the gain `gain[i]`. We can use an auxiliary array, say `altitudes`, of size `n+1` to store these values. Once this array is fully populated, a second pass is made through it to find the maximum value, which is the answer.

```java
class Solution {
    public int largestAltitude(int[] gain) {
        int n = gain.length;
        int[] altitudes = new int[n + 1];
        altitudes[0] = 0;

        // First pass: calculate all altitudes
        for (int i = 0; i < n; i++) {
            altitudes[i + 1] = altitudes[i] + gain[i];
        }

        // Second pass: find the maximum altitude
        int maxAltitude = altitudes[0];
        for (int i = 1; i <= n; i++) {
            if (altitudes[i] > maxAltitude) {
                maxAltitude = altitudes[i];
            }
        }
        
        return maxAltitude;
    }
}
```
### Algorithm
1. Create a new integer array `altitudes` of size `n + 1` to store the altitude at each point.
2. Initialize the starting altitude: `altitudes[0] = 0`.
3. Iterate through the `gain` array from `i = 0` to `n - 1`.
4. In each iteration, calculate the next altitude: `altitudes[i + 1] = altitudes[i] + gain[i]`.
5. After populating the `altitudes` array, initialize a variable `maxAltitude` to the first altitude, `altitudes[0]`.
6. Iterate through the `altitudes` array and update `maxAltitude` with the maximum value found.
7. Return `maxAltitude`.

## Single-Pass Approach with Constant Space
This is the most optimal approach. Instead of storing all the altitudes, we can calculate them one by one and keep track of the maximum altitude found so far in a single pass. This avoids the need for an extra array.
**Time:** O(n), where n is the length of the `gain` array. We iterate through the array only once. · **Space:** O(1), as we only use a few variables to store the current and maximum altitudes, regardless of the input size.
**Pros:** Highly efficient, using only constant extra space.; Solves the problem in a single iteration through the input array.
**Cons:** Combines the calculation and comparison steps, which might be slightly less intuitive for beginners than the two-pass method.
### Explanation
We can optimize the previous approach by realizing that we don't need to store all the altitudes. We only need to know the current altitude to calculate the next one, and we only need to keep track of the highest altitude seen so far. We can use two variables: `currentAltitude` to track the altitude as we iterate, and `maxAltitude` to store the maximum value found. Both are initialized to 0, the starting altitude. We then iterate through the `gain` array, updating the `currentAltitude` and comparing it with `maxAltitude` at each step. This eliminates the need for extra storage and a second pass.

```java
class Solution {
    public int largestAltitude(int[] gain) {
        int currentAltitude = 0;
        // The highest altitude starts at 0, the initial altitude.
        int maxAltitude = 0; 

        for (int g : gain) {
            currentAltitude += g;
            maxAltitude = Math.max(maxAltitude, currentAltitude);
        }

        return maxAltitude;
    }
}
```
### Algorithm
1. Initialize a variable `currentAltitude` to 0, representing the altitude at the current point.
2. Initialize a variable `maxAltitude` to 0, as this is the starting altitude and the initial highest point.
3. Iterate through the `gain` array.
4. For each `g` in `gain`, update the current altitude: `currentAltitude += g`.
5. Compare the `currentAltitude` with `maxAltitude` and update `maxAltitude` if the current one is higher: `maxAltitude = Math.max(maxAltitude, currentAltitude)`.
6. After the loop finishes, `maxAltitude` will hold the highest altitude reached during the trip. Return `maxAltitude`.

# Solutions
### JavaScript

```javascript
/** * @param {number[]} gain * @return {number} */ var largestAltitude =
  function (gain) {
    let ans = 0;
    let h = 0;
    for (const v of gain) {
      h += v;
      ans = Math.max(ans, h);
    }
    return ans;
  };

```

### Java

```java
class Solution { public int largestAltitude ( int [] gain ) { int ans = 0 , h = 0 ; for ( int v : gain ) { h += v ; ans = Math . max ( ans , h ); } return ans ; } }
```

### CPP

```cpp
class Solution { public: int largestAltitude ( vector < int >& gain ) { int ans = 0 , h = 0 ; for ( int v : gain ) h += v , ans = max ( ans , h ); return ans ; } };
```

### Python

```python
class Solution : def largestAltitude ( self , gain : List [ int ]) -> int : return max ( accumulate ( gain , initial = 0 ))
```