2
\$\begingroup\$

Write a program to implement stack which implements min a method which gives the minimum element below the top element in the stack.

const items = Symbol('Stack items');


class Stack {
  constructor() {
    this[items] = [];
  } 

  pop() {
    return this[items].pop();
  }

  push(data) {
    this[items].push(data);
  }

  size() {
    return this[items].length;
  }

  isEmpty() {
    return this.size() === 0;
  }

  peek() {
    return this[items][this.size() - 1];
  }
}

class MinStack {
  constructor(iterable) {
    this.stack = new Stack();
    this.minStack = new Stack();
    if (iterable) {
      for (let val of iterable) {
        this.push(val);
      }
    }
  } 

  min() {
    if (this.stack.isEmpty()) {
      throw new Error('Min of empty stack');    
    }
    return this.minStack.peek();
  }

  pop() {
    if (this.stack.isEmpty()) {
      throw new Error('Popping from empty stack');  
    }
    let val = this.stack.pop();
    if (val === this.minStack.peek()) {
      this.minStack.pop();
    }
    return val;
  }

  push(data) {
    if (this.minStack.isEmpty() && this.stack.isEmpty()) {
      this.minStack.push(data);
    } else if (data <= this.minStack.peek()) {
      this.minStack.push(data);
    }
    this.stack.push(data);
  }

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

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

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


const s = new MinStack();

console.log('//  Empty Stack  //');
try {
  console.log(s.min()); // Err
} catch (err) {
  console.log('Err: ' + err.message);
}


console.log('// Non-Empty Stack  //');
s.push(1);
s.push(2);
s.push(3);

console.log(s.pop() === 3);
console.log(s.min() === 1);
console.log(s.pop() === 2);
console.log(s.min() === 1);
console.log(s.pop() === 1);
try {
  console.log(s.min()); // Err
} catch (err) {
  console.log('Err: ' + err.message); // Err
}

console.log('// Using iterator  //');

const s2 = new MinStack([3, 2, 5, 1]);
console.log(s2.min() === 1);
console.log(s2.pop() === 1);
console.log(s2.min() === 2);
console.log(s2.pop() === 5);
console.log(s2.min() === 2);
console.log(s2.pop() === 2);
console.log(s2.min() === 3);
console.log(s2.pop() === 3);

/*
Space complexity: O(2n) ~ O(n)

Time complexities:
1. Construction
   Iterator: O(n) else O(1)
2. Push
   O(1) for both stacks
3. Pop
   O(1) for both stacks
4. Min
   O(1)
5. Size
   O(1)
6. isEmpty
   O(1)
*/
\$\endgroup\$
1
\$\begingroup\$

Nicely written. The space saving trick you did with min stack is especially nice.

When you push, the conditions can be a bit simpler:

push(data) {
  if (this.minStack.isEmpty() && this.stack.isEmpty()) {
    this.minStack.push(data);
  } else if (data <= this.minStack.peek()) {
    this.minStack.push(data);
  }
  this.stack.push(data);
}

The min stack will only be empty when the stack is empty, so you can drop the second condition in the first if statement. And since the else if branch does the same thing as the if branch, you can combine them:

push(data) {
  if (this.minStack.isEmpty() || data <= this.minStack.peek()) {
    this.minStack.push(data);
  }
  this.stack.push(data);
}
\$\endgroup\$
  • \$\begingroup\$ (Reading space saving trick, I searched for tricky handling of runs of identical values…) \$\endgroup\$ – greybeard Sep 21 '16 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.