716. Max Stack

Version #3 TreeMap

ComputeIfAbsent
Java 8’s Map.computeIfAbsent() method
As we learnt earlier, a multi-value map stores a collection of values for each key. Lets say we are adding a [key,value] entry to a multi-value map and the key we are adding is not present in the map. This would require for us to check for this probability before insertion and if the key is not present then we will have to instantiate a fresh collection instance as the value for this new key. Only then can we store the value against the key. Also, this check will need to be performed on every insert that we do.

employeeDOJMap.computeIfAbsent(2018,empList -> new ArrayList<>())
              .add(new Employee("Dick Newman", 35, 10000.00));

Time O(logN) for all operations
72.01 %
class MaxStack {
private class ListNode {
ListNode prev;
ListNode next;
int val;
public ListNode(int x) {
this.val = x;
}
}
private TreeMap<Integer, LinkedList<ListNode>> treeMap;
private ListNode head;
private ListNode tail;
/** initialize your data structure here. */
public MaxStack() {
// using list node to link nodes together
// treemap to get max
this.treeMap = new TreeMap<>();
this.head = new ListNode(0);
this.tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}

public void push(int x) {
// add x to the tail of the list
ListNode prevNode = tail.prev;
ListNode curr = new ListNode(x);
prevNode.next = curr;
curr.prev = prevNode;
curr.next = tail;
tail.prev = curr;
// add to treemap
// if this key has already exist, we append current node to existing list
// otherwise create a new list for this key and add
treeMap.computeIfAbsent(x, nodeList -> new LinkedList()).add(curr);
}

public int pop() {
if (this.empty()) return 0;
ListNode curr = tail.prev;
// remove curr from the doubly linked list
ListNode prevNode = curr.prev;
prevNode.next = tail;
tail.prev = prevNode;
// remove node from treeMap
LinkedList<ListNode> nodeList = treeMap.get(curr.val);
nodeList.pollLast();
if (nodeList.size() == 0) treeMap.remove(curr.val);
return curr.val;
}

public int top() {
if (this.empty()) return 0;
return tail.prev.val;
}

public int peekMax() {
if (this.empty()) return 0;
return treeMap.lastKey();
}

public int popMax() {
if (this.empty()) return 0;
Map.Entry<Integer, LinkedList<ListNode>> maxEntry = treeMap.lastEntry();
LinkedList<ListNode> nodeList = maxEntry.getValue();
ListNode curr = nodeList.pollLast();
// after we pop the last element, we remove the nodelist attached to this key
if (nodeList.size() == 0) treeMap.remove(maxEntry.getKey());
// remove this node from doubly linked list
curr.prev.next = curr.next;
curr.next.prev = curr.prev;
return curr.val;
}

private boolean empty() {
return head.next == tail;
}
}




Version #2 Two Stacks

Time push/poll/peek O(1)
Time max related O(n)

29.56 %
class MaxStack {

private Stack<Integer> numStack;
private Stack<Integer> maxStack;
/** initialize your data structure here. */
public MaxStack() {
this.numStack = new Stack();
this.maxStack = new Stack();
}

public void push(int x) {
int currMax = maxStack.isEmpty() ? x : Math.max(x, maxStack.peek());
numStack.push(x);
maxStack.push(currMax);
}

public int pop() {
if (numStack.isEmpty()) return 0;
maxStack.pop();
return numStack.pop();
}

public int top() {
return numStack.isEmpty() ? 0 : numStack.peek();
}

public int peekMax() {
return maxStack.isEmpty() ? 0 : maxStack.peek();
}

public int popMax() {
if (maxStack.isEmpty()) return 0;
Stack<Integer> temp = new Stack<>();
int currMax = maxStack.peek();
while (!maxStack.isEmpty() && numStack.peek() != currMax) {
temp.push(numStack.pop());
maxStack.pop();
}
numStack.pop(); // pop out the max
maxStack.pop();
while (!temp.isEmpty()) {
this.push(temp.pop());
}
return currMax;
}
}


Version #1 PriorityQueue
Easy to write but bad solution
Since for both pop() and popMax() are O(n)

89.62 %
class MaxStack {
private PriorityQueue<Integer> maxHeap;
private List<Integer> stack;
/** initialize your data structure here. */
public MaxStack() {
// we are using maxHeap to retrieve max in O(1)
// however when pop, we need O(n) time to remove the node from maxHeap
// when pop max, we need O(n) time to remove from list
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
stack = new LinkedList<>();
}

public void push(int x) {
// add to the head of the stack
stack.add(0, x);
maxHeap.offer(x);
}

public int pop() {
if (stack.isEmpty()) return 0;
Integer x = stack.remove(0);
maxHeap.remove(x);
return x;
}

public int top() {
if (stack.isEmpty()) return 0;
return stack.get(0);
}

public int peekMax() {
if (maxHeap.isEmpty()) return 0;
return maxHeap.peek();
}

public int popMax() {
if (maxHeap.isEmpty()) return 0;
Integer x = maxHeap.poll();
stack.remove(x); // list.remove(), scan from index 0, remove the first matched object
return x;
}
}