From Prefix Array to Clean Variables – LeetCode 1732 (Find the Highest Altitude)

Today I solved a simple but important prefix-sum type problem.

Problem Summary

A biker starts at altitude 0.You are given an array gain where:
gain[i] = net altitude change from point i to i+1. We must return the highest altitude reached during the trip.

Example

Input:

gain = [-5, 1, 5, 0, -7]

Altitude journey:

Start: 0
0 + (-5) = -5
-5 + 1 = -4
-4 + 5 = 1
1 + 0 = 1
1 + (-7) = -6

Highest altitude = 1

What I Tried First (Correct but Unnecessary)

I created a full prefix array.

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        vector<int> prefix(gain.size(),0);
        prefix[0]=gain[0];
        int temp=INT_MIN;

        for(int i=1;i<gain.size();++i){
            prefix[i] = prefix[i-1]+gain[i];
        }

        for(int x : prefix){
            temp=max(x,temp);
        }

        if(temp < 0) return 0;
        return temp;
    }
};

Why this works:

It builds cumulative altitude.Then finds the maximum.

Why it's unnecessary:

We don't need to store all prefix values.We only need the current altitude and maximum altitude.

What I Learned (Cleaner Approach)

We can solve it using just two variables.

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

        for (int g : gain) {
            current_altitude += g;
            max_altitude = max(max_altitude, current_altitude);
        }

        return max_altitude;
    }
};

Why This Is Better

1. No extra array
2. No second loop
3. Cleaner logic
4. More memory efficient

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Key Takeaway

This problem teaches an important lesson:

Prefix sum does NOT always mean creating a prefix array.Sometimes, a simple running variable is enough.Small problem, but big clarity moment.