Coding Challenge – Find maximum in a stack in o(1) time!

Question: Create getMax() function to find maximum in a stack in O(1) time!

This is widely asked technical interview for software engineers. You should know all types of data structures and how to process it.

Explanation: You will be Given a stack of integers. You need to design the special stack so we can get maximum in O(1) time complexity.

Here is the sample input:

Input:

2
5
1
64   

Output: 64

Algorithm to solve this challenge:

We will have two stacks, one stack which holds all of given integers, and maxesStack holds the max elements.

maxesStack will have our max up to date in constant time as we push() and pop():

Whenever we push() a new item, we check to see if it’s greater than or equal to the current max, which is at the top of maxesStack. If it is, we also push() it onto maxesStack.

Whenever we pop(), we also pop() from the top of maxesStack if the item equals the top item in maxesStack.

And as maxesStack is up to date, when we call getMax(), we will get max element within O(1) time!

Now we have pseudo code so we can put that solution into actual code. I am using javascript to solve the challenge but you can use this pseudo code in any other programming language!

Solution:

class maxStack {
  constructor() {
    this.s = [];
    this.maxS = [];
  }

  
  push(int) {
    this.s.push(int);
    if (Math.max(this.maxS) === null || int >= Math.max.apply(null, this.maxS)) {
      this.maxS.push(int);
    }
  }

  
  pop() {
    const item = this.s.pop();
    if (item === Math.max.apply(null, this.maxS)) {
      this.maxS.pop();
    }
    return item;
  }

  getMax() {
    return Math.max.apply(null, this.maxS);
  }

}

const test = new maxStack();
test.push(2);
test.push(4);
test.push(6);
test.pop(6);
console.log(test.getMax());

Play Code in the Editor Here: