Lowest Point on the Trail

MediumdesignAlso known as Min Stack

A hiking app records your route as a list of waypoints, each with its altitude. Walking forward adds a waypoint. When you hit a dead end and retrace your steps, the app drops the waypoints you walk back over, so the list is always the path from the trailhead to where you stand.

The app shows two numbers on screen at all times: your current altitude and the lowest altitude on your current path. They are refreshed after every step, so each must be instant, even on a path with thousands of waypoints.

Your task

Write a class TrailLog with these methods:

step(altitude): add a waypoint at the end of the path.
back(): remove the most recent waypoint.
current(): return the altitude of the most recent waypoint.
lowest(): return the lowest altitude among all waypoints still on the path.

Every method must run in O(1) time.

class TrailLog

Examples

Example 1

Input

new TrailLog()
.step(340)
.step(280)
.step(410)
.lowest()
.back()
.back()
.lowest()
.current()

Output

[null, null, null, null, 280, null, null, 340, 340]

Why

The hiker walks to 340 m, 280 m, then 410 m. The lowest point on the path is 280. Backing off 410 changes nothing, but backing off 280 too leaves only 340 on the path, so the lowest point is now 340 and the hiker stands at 340.

Constraints

1 ≤ number of method calls ≤ 1,000
-1,000 ≤ altitude ≤ 10,000 (metres; negative means below sea level). Altitudes may repeat.
back, current and lowest are only called when the path has at least one waypoint.

Start with brute force

Keep the altitudes in an array and compute lowest() by scanning the whole array each time it is called.

That makes lowest() O(n). The screen refreshes after every step, so a hike of n waypoints costs O(n²) in total. A single low variable is fast but wrong: it cannot recover the previous low after back() removes the lowest waypoint.

Hints

0 of 4 shown

Hint 1
Walk to 500, then 200. The lowest is 200. Now back off 200. If you only kept one variable low = 200, how would you know the new lowest is 500?
Hint 2
When the lowest waypoint is removed, you need the lowest of what remains, and that is exactly the lowest the path had before that waypoint was added. That earlier value must still be stored somewhere.
Hint 3
The path only changes at its end, so it is a stack. What if every entry also remembered the lowest altitude of the path up to and including itself?
Hint 4
Push pairs (altitude, lowestSoFar), where lowestSoFar = min(altitude, lowestSoFar of the entry below). back pops a pair, current reads the top altitude, lowest reads the top's lowestSoFar.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

The path grows and shrinks only at its end, so it is a stack. The hard part is lowest() after a back(). The fix: when you push a waypoint, also store the lowest altitude of the path at that moment. Popping then restores the old answer for free, because the entry below still holds it.

Trace the example:

step 340. Nothing below, so push (340, 340).
step 280. min(280, 340) = 280. Push (280, 280).
step 410. min(410, 280) = 280. Push (410, 280). lowest() reads the top: 280.
back: pop (410, 280). back: pop (280, 280). The top is now (340, 340).
lowest() = 340 and current() = 340.

Each entry is a snapshot of the answer for the path that ends at it. You never recompute anything; you just read the top.

Reference solution

class TrailLog {
  constructor() {
    this.path = []; // entries: [altitude, lowest altitude up to here]
  }
  step(altitude) {
    const below = this.path.length ? this.path[this.path.length - 1][1] : altitude;
    this.path.push([altitude, Math.min(altitude, below)]);
  }
  back() {
    this.path.pop();
  }
  current() {
    return this.path[this.path.length - 1][0];
  }
  lowest() {
    return this.path[this.path.length - 1][1];
  }
}

class TrailLog:
    def __init__(self):
        self.path = []  # entries: (altitude, lowest altitude up to here)
 
    def step(self, altitude):
        below = self.path[-1][1] if self.path else altitude
        self.path.append((altitude, min(altitude, below)))
 
    def back(self):
        self.path.pop()
 
    def current(self):
        return self.path[-1][0]
 
    def lowest(self):
        return self.path[-1][1]

TimeO(1)Every method does one push, one pop, or one read at the top of the stack.

SpaceO(n)Two numbers per waypoint on the path.

Learn the idea: Stacks Designing Data Structures

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code