Find the maximum element in a stack in O(1) (constant time).
Design a stack to get the maximum element from a stack in constant time.
For example:
To understand this problem, let’s take an example. Suppose, the following elements are pushed in a stack.
push(4)
push(3)
push(9)
push(2)
push(8)
getMax() ( Now, if I call a method to return max element then it should return 9 in O(1)).
pop()
pop()
pop()
getMax() (After three pop operations, If I again call a method to get max element then it should return 4 in O(1)).
Stack
A stack is a Last In First Out (LIFO) data structure. The element which we pushed at last in a stack is the first element to be popped out from a stack.
So whenever the getMax() method is called how do we return the maximum element from a stack in O(1).
This problem is similar to find the minimum element from a stack in O(1).
Find maximum element in stack in O(1) video tutorial
How to Get Maximum Element form a Stack in O(1)
We can solve this problem by using two stacks. Here are the steps to solve this problem.
i) Declare two stacks. In one stack, we push value as it is. In the second stack, we only push the maximum element present at that time.
|
1 2 |
private Stack<Integer> st = new Stack<>(); private Stack<Integer> maxSt = new Stack<>(); |
ii) Whenever we perform push operation in a stack.
a) Push the value as it is in a first stack.
b) For the second stack, push only the maximum value. To get the maximum value, Compare the current value with the value present at the top of the stack.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//Push operation public void push(int data) { //Declare max variable int max = data; /* If the value in max stack is not empty, and value present at the top of the stack is greater than the value we are going to push. Then assign the value present at the top of the stack to the max variable. */ if(!maxSt.isEmpty() && max < maxSt.peek()) { max = maxSt.peek(); } st.push(data); maxSt.push(max); } |
After this push operation, this is the value present in stack and max stack.
Now you can see, if I call the peek() method on the second stack it can always return the maximum element from a stack in O(1).
Find the Maximum Element in a Stack in O(1) – Java Code
I have already explained its algorithm. Let’s write a java code to implement this algorithm.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
/* Get maximum element from a stack in O(1). */ public class MaxElementInStack { //Declare two stacks private Stack<Integer> st = new Stack<>(); private Stack<Integer> maxSt = new Stack<>(); public void push(int data) { int max = data; if(!maxSt.isEmpty() && max < maxSt.peek()) { max = maxSt.peek(); } st.push(data); maxSt.push(max); } public void pop() { st.pop(); maxSt.pop(); } public int getMax() { return maxSt.peek(); } public static void main(String[] args) { MaxElementInStack maxElem = new MaxElementInStack(); maxElem.push(4); maxElem.push(3); maxElem.push(9); maxElem.push(2); maxElem.push(8); System.out.println(maxElem.st); System.out.println(maxElem.maxSt); System.out.println(" Max Element " + maxElem.getMax()); maxElem.pop(); maxElem.pop(); maxElem.pop(); System.out.println(maxElem.st); System.out.println(maxElem.maxSt); System.out.println(" After 3 pop operation " + maxElem.getMax()); } } |
