Find the Highest Altitude - Practice Coding Problems

Find the Highest Altitude - Problem

A biker is going on a road trip consisting of n + 1 points at different altitudes. The biker starts at point 0 with altitude 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 reached during the trip.

Input & Output

Example 1 — Basic Case

$ Input: gain = [-3,1,5,-3,1]

› Output: 3

💡 Note: Altitudes: 0 → -3 → -2 → 3 → 0 → 1. The highest altitude reached is 3.

Example 2 — All Negative Gains

$ Input: gain = [-4,-3,-2,-1]

› Output: 0

💡 Note: Starting altitude 0 is the highest since all gains are negative: 0 → -4 → -7 → -9 → -10.

Example 3 — All Positive Gains

$ Input: gain = [1,2,3]

› Output: 6

💡 Note: Altitudes increase continuously: 0 → 1 → 3 → 6. Maximum is 6.

Constraints

n == gain.length
1 ≤ n ≤ 100
-100 ≤ gain[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Array of altitude gains between consecutive points

Process

Calculate altitude at each point using running sum

Output

Return the maximum altitude reached

Key Takeaway

🎯 Key Insight: Use prefix sum to calculate running altitude while tracking the maximum value encountered

Asked in

A Amazon 15 G Google 12 M Microsoft 8

The key insight is to use a running sum (prefix sum) to track current altitude while maintaining the maximum altitude seen. The optimal approach processes the array in a single pass with O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum - Single Pass Optimization	O(n)	O(1)	Calculate running altitude while tracking maximum in one pass
Brute Force - Recalculate Each Altitude	O(n²)	O(1)	For each point, sum all previous gains to get current altitude

Prefix Sum - Single Pass Optimization — Algorithm Steps

Initialize current altitude to 0 and max altitude to 0
For each gain value, add it to current altitude
Update maximum altitude if current is higher

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with current=0, max=0

Process Each Gain

Add gain to current altitude

Track Maximum

Update max if current is higher

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* gain, int size) {
    int currentAltitude = 0;
    int maxAltitude = 0;
    
    for (int i = 0; i < size; i++) {
        currentAltitude += gain[i];
        if (currentAltitude > maxAltitude) {
            maxAltitude = currentAltitude;
        }
    }
    
    return maxAltitude;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array
    int gain[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        gain[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(gain, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the gain array of length n

✓ Linear Growth

Space Complexity

O(1)

Only using two variables to track current and maximum altitude

✓ Linear Space

99.6K Views

Medium Frequency

~10 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum - Single Pass Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler