Max Min Stack

We've already seen how to implement a stack using linked lists or dynamic arrays. Your challenge is going to be to build on this base implementation to create a stack with additional superpowers.

Create a MaxMinStack class that will return the maximum and minimum value from the stack at any time using getStackMax and getStackMin functions.

You will start with the MaxMinStack class below, which already works as a basic stack. You can add or update any method necessary for this to work. The stack will only be passed integers, and pop, peek, getStackMax and getStackMin won't be called on an empty stack.

Breakdown

Approach and test strategy

Keep extrema history synchronized with stack history

Read the approach, boundary cases, and complexity

Support push, pop, peek, minimum, and maximum without rescanning the entire stack for each extrema query. Retain enough history to restore the previous minimum and maximum when the newest entry is removed. Repeated extrema require separate occurrences or counts: popping one copy must not discard another copy still present below it. The lesson does not call pop, peek, or extrema methods on an empty stack.

Cases to check

Push a new minimum and maximum, then pop them to restore older extrema.
Repeat the same minimum or maximum before popping one copy.
Verify that push returns the pushed item as the starter contract specifies.

Cost model

With synchronized extrema state, the required stack operations can take O(1) time each. Stored values and extrema history require O(n) total storage.

Programming languages for this lesson

Starter code and reference implementations are available in:

The editor shows which of these languages can run on this deployment.

Follow teacher

Table of Contents

Validate My Answer

A brute force solution would be to iterate the stack to track the max/min integer. This would require O(n) time, so we should be looking for solutions better than this.
The max and min can increase or decrease at any point depending on what integer you push/pop. Make sure you account for this.
You can solve this in O(1) time and O(n) space.

Follow teacher

Table of Contents

Test Results

Run your code and see results here...

class MaxMinStack {
  // Any of the initial methods can be updated
  constructor() {
    this.stack = [];
  }
  peek() {
    return this.stack[this.stack.length - 1];
  }
  push(item) {
    this.stack.push(item);
    return item;
  }
  pop() {
    return this.stack.pop();
  }

  // You must implement the methods below
  getStackMax() {
    // Return the largest integer currently in the stack (don't remove it)
  }
  getStackMin() {
    // Return the smallest integer currently in the stack (don't remove it)
  }
}

Max Min Stack

Create a MaxMinStack class that will return the maximum and minimum value from the stack at any time using getStackMax and getStackMin functions.

class MaxMinStack {
  // Any of the initial methods can be updated
  constructor() {
    this.stack = [];
  }
  peek() {
    return this.stack[this.stack.length - 1];
  }
  push(item) {
    this.stack.push(item);
    return item;
  }
  pop() {
    return this.stack.pop();
  }

  // You must implement the methods below
  getStackMax() {
    // Return the largest integer currently in the stack (don't remove it)
  }
  getStackMin() {
    // Return the smallest integer currently in the stack (don't remove it)
  }
}