Find the Highest Altitude

Easy
195.

Find the Highest Altitude

EasyArrayPrefix SumAmazonGoogle

Find the Highest Altitude is an easy coding problem on arrays and prefix sum, asked in Amazon and Google interviews.

A biker rides through n + 1 points, starting at altitude 0. You are given an array gain of length n, where gain[i] is the net altitude change between point i and point i + 1.

Return the highest altitude reached at any 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 never rise above the starting point.

Example 3

Input
gain = [3,3]
Output
6

Constraints

  • 1 <= gain.length <= 40
  • -100 <= gain[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} gain
 * @return {number}
 */
var largestAltitude = function(gain) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Find the Highest Altitude — Solution in Python, Java & C++

Find the Highest Altitude solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find the Highest Altitude is an easy coding problem on arrays and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A biker rides through n + 1 points, starting at altitude 0. You are given an array gain of length n, where gain[i] is the net altitude change between point i and point i + 1.

Return the highest altitude reached at any 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 never rise above the starting point.

Example 3

Input: gain = [3,3]
Output: 6

Constraints

  • 1 <= gain.length <= 40
  • -100 <= gain[i] <= 100

Hints for Find the Highest Altitude

  1. Hint 1

    Altitudes are the prefix sums of gain, starting from 0.

  2. Hint 2

    Track the running sum and the best value seen — but seed the best with 0, since the start counts as a point.

How to solve Find the Highest Altitude

Altitudes are prefix sums of gain starting at 0; track the running sum and the best seen, seeded with 0.

Approach

  1. Start cur = best = 0.
  2. For each gain, add it to cur and update best.

Why it works

The altitude after step i is the sum of the first i gains, and the starting point counts as a visited altitude, which is why best begins at 0 rather than at the first prefix.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Seeding best with the first prefix sum misses the case where every altitude is negative and the answer is 0.

Reference solution

Python

def largestAltitude(gain):
    cur = best = 0
    for g in gain:
        cur += g
        if cur > best:
            best = cur
    return best

Java

public static int largestAltitude(int[] gain) {
    int cur = 0, best = 0;
    for (int g : gain) {
        cur += g;
        if (cur > best) best = cur;
    }
    return best;
}

C++

int largestAltitude(vector<int>& gain) {
    int cur = 0, best = 0;
    for (int g : gain) {
        cur += g;
        if (cur > best) best = cur;
    }
    return best;
}

JavaScript

var largestAltitude = function(gain) {
    let cur = 0, best = 0;
    for (let i = 0; i < gain.length; i++) {
        cur += gain[i];
        if (cur > best) best = cur;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum