Topic: Learning notes

LeetCode 1732: Find the Highest Altitude in TypeScript

Track current altitude and the highest altitude so far in one scan with O(n) time and O(1) auxiliary space.

This problem does not need an array of every altitude. Two values are enough: the current altitude and the highest altitude seen so far. For each road segment, update the current altitude, then compare it with the current maximum.

Problem

Original problem: LeetCode 1732: Find the Highest Altitude

A cyclist starts at altitude 0. gain[i] is the altitude change for road segment i. Return the highest altitude reached during the trip, including the starting point.

For example, [-5, 1, 5, 0, -7] produces altitudes [0, -5, -4, 1, 1, -6], so the answer is 1.

No need to keep every altitude

One approach builds an array of every altitude and finds its maximum. Each segment, however, produces only one new altitude, and the only question is whether it exceeds the maximum already seen.

Keep the current altitude and the maximum. Each value in gain can then be handled as it arrives.

function largestAltitude(gain: number[]): number {
  let currentAltitude = 0;
  let maxAltitude = currentAltitude;

  for (let index = 0; index < gain.length; index += 1) {
    currentAltitude += gain[index];
    maxAltitude = Math.max(maxAltitude, currentAltitude);
  }

  return maxAltitude;
}

Why the loop is correct

At the start of each iteration, currentAltitude is the altitude at the current point, and maxAltitude is the highest altitude from the start through that point.

Adding gain[index] moves currentAltitude to the next point. Math.max() then compares that new altitude with the previous maximum, so maxAltitude also covers the next point. At the end, it has considered the starting point and every road-segment endpoint, which makes the returned value the highest altitude of the trip.

The starting altitude is 0, so maxAltitude must also start at 0. If every segment descends, the answer remains 0.

Minimal verification

import assert from "node:assert/strict";

assert.strictEqual(largestAltitude([-5, 1, 5, 0, -7]), 1);
assert.strictEqual(largestAltitude([-4, -3, -2, -1, 4, 3, 2]), 0);
assert.strictEqual(largestAltitude([3, -2, 4, -10]), 5);

The second case checks that the starting point is part of the answer. The third checks that the highest point does not have to be the final point.

Complexity

The function scans the array once, so time is O(n). It uses only currentAltitude and maxAltitude, so auxiliary space is O(1).

These are changing variables, not constants. Space complexity counts storage locations, not whether a variable changes.

Common mistakes

• Forgetting the starting altitude of 0 and returning a negative number for an all-descending trip.
• Comparing the maximum before updating the current altitude, which skips the point just reached.
• Returning the final altitude instead of the highest altitude.
• Building every altitude when later code does not need the intermediate values.

Transferable idea

This is a common streaming split. currentAltitude stores the current state, and maxAltitude stores the best result so far. When data can be read in order, keeping every historical value is often unnecessary.

External references

• LeetCode 1732: Find the Highest Altitude: original problem statement, examples, and constraints.
• TypeScript Handbook: More on Functions: function parameter and return-type syntax.
• Node.js: assert.strictEqual(): assertion APIs for checking expected results.