Constant time max operation on stack

Constant time max operation on stack

We understood stack data structure, operations on it and some examples problems which can be solved using stack. Let’s take problem which is actually based on stack and with the help of other data structures, how can make it more efficient for certain function. Today’s problem is to implement constant time max operation on stack.

To elaborate, you have been given a stack, where elements are pushed and popped randomly. At any given point of time, you have to tell max of all the elements present in stack.
For example : we have stack, we push 5,3,1, current max in stack is 5; we push 6 next, current max is 6 now. How about we pop 6 back. Current max goes back to 5 again.

Constant time max operation: Line of thoughts

Push and pop operation in a stack are already constant time operations. Let’s concentrate on max operation.
If always just pushed on to stack, it would have been easy to just keep track of ma of all the elements we pushed on to stack. However if we are popping out from stack, this may not be as easy. Max will change if the element just popped from stack was current max. What can we do? We keep track of previous max just before the current max. What if next operation is again pop and it pops out the new current max. Again, we have to keep track of previous to previous max.
Are you getting some hint here? We have to keep track of all the max we ever saw while operating on stack in reverse order. That means the max we saw the last, goes out first. LIFO pattern and what better data structure than stack to implement that.

Idea is to have an auxiliary stack which stores all the max seen till a given point of time. Top of this auxiliary stack would be current max. What happens when pop happens on original array? We check if popped element is equal to top element of auxiliary array, that means popped element was current max. So we pop that from auxiliary stack too.

Let’s take an example and see if it works? To start with, both stacks are empty. Now, you add 2 as first element on to stack. Since auxiliary stack is empty, we add 2 on to that stack too.

Push 3 on to stack. Push operation so check if current top of aux stack is less than new element pushed. If yes, push new element to aux stack too.

Push 5 on to stack. Again, push operation and new push element is greater than top of aux stack, we push 5 there too.

Now, push 1. Tricky case. Push 1 on to original stack, but since new element is less than current top of aux stack, nothing gets pushed on aux stack.

Pop from stack now. 1 is popped, it is not equal to current top on aux stack, nothing happens.

Pop from stack again, this time popped element is equal to current max, so we have pop from aux stack too. If we are asked max at this point of time, answer would be 3.

Constant time max operation on stack : Implementation

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> auxStack;

    public MaxStack() {
        stack = new Stack();
        auxStack = new Stack();
    }

    public void push(int x) {
        int max = auxStack.isEmpty() ? x : auxStack.peek();
        //Push on max stack only if max value is being changed.
        if (max <= x) auxStack.push(x);
        stack.push(x);
    }

    public int pop() {
        int returnValue = stack.pop();
        //Pop from aux stack only if ax value is being popped out.
        if(auxStack.peek() == returnValue) {
            auxStack.pop();
        }
        return returnValue;
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return auxStack.peek();
    }

    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack();
        while (top() != max) buffer.push(pop());
        pop();
        while (!buffer.isEmpty()) push(buffer.pop());
        return max;
    }
}

Complexity of implementation of constant time max operation stack is O(n) in terms of space, with O(1) time complexity for push, pop and max operation.

Wait, interviewer is not satisfied with this only. What we solve is just reporting the max element in stack at a given point of time. What if we were asked to implement pop max element from stack? Well, first of all finding the max element works as it is. However, popping max element requires popping out all element before max, popping out max and then pushing back all other elements again. Quite a lot of work, even when max operation is O(1).

Which data structure allows us to remove an element in constant time? It’s doubly link list. Once you know which node is to be removed, all we have to do is link previous node to next node. If we implement our original stack as doubly linked list, popping max from stack is O(1) operation without moving any other element on stack.

However finding the node in doubly linked list itself is O(n) operation. Back to square one. What would be helpful is that instead of just storing the max element, we store node address of max in doubly linked list. So in our aux stack, we do not store primitive data type, but a pointer to node which is current max.

Let’s see how it works? We follow the same process of finding the max as explained in earlier solution. It starts with pushing element 2 on to stack. This creates the first node on DLL and stores the pointer on stack.

Now, we push 3 on to stack. Since this is greater than current max being pointed to by top of aux stack, we push that to DLL and store the pointer as max pointer on aux stack.

As for 3, same thing happens when 5 is pushed on to stack.

Since new element pushed is less than current max, it’s pointer is not pushed on to aux stack.
constant time max operation on stack

After pushing 1, we want to pop max. Step 1 would be to fetch the node pointer for current max. Go to that node in doubly linked list. Remove that node from DLL and then remove the pointer from top of stack.

Make a note that whenever, new pushed element is equal to current max, push that on aux stack too. Why?

Let’s see the implementation of this method using doubly linked list.

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStackDLL {
    private DoubleLinkedList dll;
    private Stack<ListNode<Integer>> auxStack;

    public MaxStackDLL() {
        auxStack = new Stack();
        dll = new DoubleLinkedList();
    }

    public void push(int x) {
        int max = auxStack.isEmpty() ? x : auxStack.peek().getData();
        //Push on max stack only if max value is being changed.
        ListNode<Integer> newNode = dll.insertAtHead(x);
        if (max <= x) auxStack.push(newNode);
    }

    public int pop() {
        ListNode<Integer> returnValue = dll.deleteAtHead();

        //Pop from aux stack only if ax value is being popped out.
        if(auxStack.peek() == returnValue) {
            auxStack.pop();
        }
        return returnValue.getData();
    }

    public int peekMax() {
        return !auxStack.isEmpty() ? auxStack.peek().getData() : -1;
    }

    public int popMax() {
        return auxStack.isEmpty() ? -1 : dll.deleteNode(auxStack.pop()).getData();
    }
}

Doubly linked list class is as follows

package com.company;

/**
 * Created by sangar on 22.9.18.
 */
public class DoubleLinkedList {

    ListNode<Integer> head;

    public DoubleLinkedList(){
        head = null;
    }

    public boolean isEmpty(){
        return this.head == null;
    }

    public ListNode<Integer> insertAtHead(int data){
        if(this.isEmpty()) {
            this.head = new ListNode<Integer>(data);
            return this.head;
        }
        /*
            We are inserting node at head. So following things happen
            1. Create a new node.
            2. Set next of new pointer to current head.
            3. Set prev of head to new node
            4. Make new node as head of linked list
          */
        //First two steps are done here
        ListNode<Integer> newNode = new ListNode<Integer>(data,this.head, null);
        //Step 3.
        this.head.setPrev(newNode);
        //Step 4.
        this.head = newNode;

        return this.head;
    }

    public ListNode<Integer> deleteAtHead(){
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node at head. So following things happen
            1. Set temporary node point to head.
            2. Move head to next of node.
            3. Set prev of new head to NULL.
            4. Free the temp node.
          */
        ListNode<Integer> tempNode = this.head;
        this.head = this.head.getNext();
        this.head.setPrev(null);

        return tempNode;
    }

    public ListNode<Integer> deleteNode(ListNode<Integer> node){
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node in between. So following things happen
            1. If node has prev, set node.prev.next = node.next.
            2. If node has next, set node.next.prev = node.prev
        */
        if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
        if(node.getNext() != null) node.getNext().setPrev(node.getPrev());

        return node;
    }
}

ListNode class is as follows

package com.company;

/**
 * Created by sangar on 22.9.18.
 */
public class ListNode<T> {
    private T data;

    private ListNode<T> next;
    private ListNode<T> prev;

    public ListNode(T data){
        this.data = data;
        next = null;
        prev = null;
    }

    public ListNode(T data, ListNode<T> next, ListNode<T> prev){
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    public ListNode<T> getNext(){
        return this.next;
    }

    public ListNode<T> getPrev(){
        return this.prev;
    }

    public void setPrev(ListNode<T> newNode){
        this.prev = newNode;
    }

    public void setNext(ListNode<T> newNode){
        this.next = newNode;
    }

    public T getData(){
        return this.data;
    }
}

Tester class is given below. Can you add more test cases to this?

package test;

import com.company.MaxStackDLL;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStackTest {


    MaxStackDLL tester = new MaxStackDLL();
    @Test
    public void popMaxTest() {

        tester.push(2);
        tester.push(3);
        tester.push(5);
        tester.push(1);

        assertEquals(5, tester.popMax());
        assertEquals(3, tester.popMax());
    }
}

Time complexity of push, pop and popMax is O(1). There is additional space requirement which is O(n).

Please share if there is something wrong or missing. If you are interested in taking personalized coaching by our experienced coaches, please reach out to us at communications@algorithmsandme.com