# #1 Min Max Stack Construction

###### tags:`Stack` `Medium`

## Problem

[155. Min Stack](https://leetcode.com/problems/min-stack/)

Write a `MinMaxStack` class for a Min Max Stack. The class should support:
* Pushing and popping values on and off the stack.
* Peeking at the value at the top of the stack.
* Getting both the minimum and the maximum values in the stack at any given point in time.

:::warning
All class methods, when considered independently, should run in constant time and with constant space.
:::

### Sample Usage

// All operations below are performed sequentially.
MinMaxStack(): - // instantiate a MinMaxStack
push(5): -
getMin(): 5
getMax(): 5
peek(): 5
push(7): -
getMin(): 5
getMax(): 7
peek(): 7
push(2): -
getMin(): 2
getMax(): 7
peek(): 2
pop(): 2
pop(): 7
getMin(): 5
getMax(): 5
peek(): 5

<br>

:::spoiler **Optimal Space & Time Complexity**

All methods: O(1) time | O(1) space

:::

<br>

:::spoiler Hint 1
You should be able to push values on, pop values off, and peek at values on top of the stack at any time and in constant time, using constant space. What data structure maintains order and would allow you to do this?
:::

<br>

:::spoiler Hint 2
You should be able to get the minimum and maximum values in the stack at any time and in constant time, using constant space. What data structure would allow you to do this?
:::

<br>

:::spoiler Hint 3
Since the minimum and maximum values in the stack can change with every push and pop, you will likely need to keep track of all the mins and maxes at every value in the stack.
:::

<br>

<hr/>

## Solutions

### Official

// Copyright © 2022 AlgoExpert LLC. All rights reserved.
class MinMaxStack {
  constructor() {
    this.minMaxStack = [];
    this.stack = [];
  }
    
  // O(1) time | O(1) space
  peek() {
    return this.stack[this.stack.length - 1];
  }
    
  // O(1) time | O(1) space
  pop() {
    this.minMaxStack.pop();
    return this.stack.pop();
  }
    
  // O(1) time | O(1) space
  push(number) {
    const newMinMax = {min: number, max: number};
    if (this.minMaxStack.length) {
      const lastMinMax = this.minMaxStack[this.minMaxStack.length - 1];
      newMinMax.min = Math.min(lastMinMax.min, number);
      newMinMax.max = Math.max(lastMinMax.max, number);
    }
    this.minMaxStack.push(newMinMax);
    this.stack.push(number);
  }
    
  // O(1) time | O(1) space
  getMin() {
    return this.minMaxStack[this.minMaxStack.length - 1].min;
  }
    
  // O(1) time | O(1) space
  getMax() {
    return this.minMaxStack[this.minMaxStack.length - 1].max;
  }
    
// Do not edit the line below.
exports.MinMaxStack = MinMaxStack;

<br>

---

### Everyone's

:::spoiler 月

:::

<br>

:::spoiler 東

class MinMaxStack {
  stack = [];
  minMaxStack = [];

  peek() {
    return this.stack[this.stack.length - 1];
  }

  pop() {
    this.minMaxStack.pop();
    return this.stack.pop();
  }

  push(number) {
    const currMinMax = this.minMaxStack[this.minMaxStack.length - 1]
    let newMin = number, newMax = number;
    if(this.minMaxStack.length){
      newMin = Math.min(currMinMax.min, number);
      newMax = Math.max(currMinMax.max, number);
    }
    this.minMaxStack.push({min: newMin, max: newMax});
    this.stack.push(number);
  }

  getMin() {
    return this.minMaxStack[this.minMaxStack.length - 1].min;
  }

  getMax() {
    return this.minMaxStack[this.minMaxStack.length - 1].max;
  }
}

:::

<br>

:::spoiler YC

class MinMaxStack {
  constructor(){
    this.stack = [];
    this.minMaxStack = []; //[{min, max}]
  }
  peek() {
    return this.stack[this.minMaxStack.length - 1];
  }

  pop() {
    this.minMaxStack.pop();
    return this.stack.pop();
    
  }

  push(number) {
    // Write your code here.
    this.stack.push(number);

    if(!this.minMaxStack.length){
      this.minMaxStack.push({ min: number, max: number});
    }
    else{
      const latestMinMax = this.minMaxStack[this.minMaxStack.length - 1];
      this.minMaxStack.push(
        {
          min: Math.min(number, latestMinMax.min), 
          max: Math.max(number, latestMinMax.max)
        }
      )
        
    }
  }

  getMin() {
    return this.minMaxStack[this.minMaxStack.length - 1].min;
  }

  getMax() {
    return this.minMaxStack[this.minMaxStack.length - 1].max;
  }
}

// Do not edit the line below.
exports.MinMaxStack = MinMaxStack;

:::

<br>

:::spoiler SOL

class MinMaxStack {
  constructor(){
    this.minMaxStack = []
    this.stack = []
  }
  
  peek() {
    return this.stack[this.stack.length-1]
  }

  pop() {
    this.minMaxStack.pop()
    return this.stack.pop();
  }

  push(number) {
    this.stack.push(number);
    if(this.minMaxStack.length === 0){
      this.minMaxStack.push({min:number,max:number})
      return;
    }
    const{min, max} = this.minMaxStack[this.minMaxStack.length-1]
    this.minMaxStack.push({
      min: Math.min(min,number),
      max: Math.max(max,number)
    })
  }

  getMin() {
   return this.minMaxStack[this.minMaxStack.length-1].min
  }

  getMax() {
    return this.minMaxStack[this.minMaxStack.length-1].max
  }
}

:::

<br>

:::spoiler Hao
- All class methods, when considered independently, should run in constant time and with constant space.

class MinMaxStack {
  constructor() {}

  stack = [];

  peek() {
    return this.stack[this.stack.length - 1];
  }

  pop() {
    return this.stack.pop();
  }

  push(number) {
    this.stack.push(number);
  }

  getMin() {
    return this.stack.reduce((min, each) => (each < min ? each : min));
  }

  getMax() {
    return this.stack.reduce((max, each) => (each > max ? each : max));
  }
}

:::

<br>

---

## Supplement / Discussion

[Stack: 能夠在O(1)取得最小值的MinStack](https://alrightchiu.github.io/SecondRound/stack-neng-gou-zai-o1qu-de-zui-xiao-zhi-de-minstack.html)