Tracking the Current Maximum Element in the Stack

Last Updated on October 10, 2022 by Gokul Kannan

Problem Statement:

You will be given a stack of integer values. You have to keep a track of the maximum value in the stack. For instance, the element that is currently at the top of the stack may be the maximum element in the stack. However, if that element is removed from the stack, the maximum value in the stack might now change. So, you always have to return the current maximum.

Example

Consider the stack given below.

In this stack, the maximum element is 50 which is also the top of the stack.

Now, if we pop 50 from the top of the stack, the maximum element will now be 40.

If we pop an element from the top of the stack again, we still get 40 as the maximum value.

So, this is what you have to do. You just have to keep a track of the maximum element in the stack.

Brute Force Approach

Consider the stack shown below.

In this track, if we have to return the maximum element, we will simply traverse the stack and find the maximum element of the stack.

So, if we traverse this stack, we can say that 50 is the maximum element of the stack.

Note: In Java, we can traverse the stack using an iterator and the hasNext() method. In C++, we will have to create a copy of the original stack and pop all the elements from that copy stack to traverse it.

Time Complexity:

The time complexity for finding the maximum element one time is O(N) as we have to traverse the entire stack.

Space Complexity:

If we traverse the same stack using an iterator (in Java), the auxiliary space is O(1). In C++, we have to create a copy of the original stack and pop all the elements from it to traverse the stack. So, the space complexity, in that case, will be O(N).

Optimized Approach

In this approach, we will use an auxiliary stack that will maintain the maximum element at every stage. Consider that there are 2 stacks. We have the main stack and we have another stack called the max_stack.

So, when we insert an element into the main stack for the first time, we will also insert that element into the max_stack. So, if we insert 10, we insert 10 in both stacks.

Now, let us say that the next element is 20. So, we insert this element into the main stack.

Now, we will compare the current element 20 to the top of the max_stack and will store the maximum element on the top of the max_stack. So, 20 is greater than the current top of the max_stack i.e. 10. So, we will insert 20 in the max_stack also.

Let us say the next element is 5. So, we insert element 5 into the main stack.

Again, we compare the current element i.e. 5 to the top of the max stack. Since the top of the max_stack i.e. 20 is greater than the current element 5, we will insert 20 only into the max_stack.

So, basically, the top of the max_stack shows the current maximum element of the stack.

Now, let us insert 30 into the stack. So, you now understand that 30 will be inserted in the main stack and since it is also larger than the top of the max_stack, 30 will be inserted in the max_stack too.

Now, let us pop an element from the main stack.

So, whenever you pop an element from the main stack, you have to pop an element from the max_stack too.

So, now after removing 30, the maximum value in the stack should be 20. If we see the top of the max_stack, it is also 20. So, the top of the max_stack always returns the maximum element in the main stack.

So, we hope that you have understood the procedure that we have to follow while pushing an element and popping an element from the stack.

Now that we have understood the complete procedure, let us write the code for the same.

Code Implementation

#include <bits/stdc++.h>
using namespace std;

class StackWithMax
{

	stack<int> mainStack;

	stack<int> trackStack;

public:
	void push(int x)
	{
		mainStack.push(x);
		if (mainStack.size() == 1)
		{
			trackStack.push(x);
			return;
		}

		if (x > trackStack.top())
			trackStack.push(x);
		else
			trackStack.push(trackStack.top());
	}

	int getMax()
	{
		return trackStack.top();
	}

	void pop()
	{
		mainStack.pop();
		trackStack.pop();
	}
};

int main()
{
	StackWithMax s;
	s.push(10);
	cout << s.getMax() << endl;
	s.push(20);
	cout << s.getMax() << endl;
	s.push(5);
    cout << s.getMax() << endl;
	s.push(30);
	cout << s.getMax() << endl;
	return 0;
}

import java.util.*;
class Main {

static class StackWithMax
{
	static Stack<Integer> mainStack = new Stack<Integer> ();

	static Stack<Integer> trackStack = new Stack<Integer> ();

static void push(int x)
	{
		mainStack.push(x);
		if (mainStack.size() == 1)
		{
			trackStack.push(x);
			return;
		}
		if (x > trackStack.peek())
			trackStack.push(x);
		else
			trackStack.push(trackStack.peek());
	}

	static int getMax()
	{
		return trackStack.peek();
	}

	static void pop()
	{
		mainStack.pop();
		trackStack.pop();
	}
};

public static void main(String[] args)
{
	StackWithMax s = new StackWithMax();
	s.push(10);
	System.out.println(s.getMax());
	s.push(20);
	System.out.println(s.getMax());
	s.push(5);
    System.out.println(s.getMax());
	s.push(30);
	System.out.println(s.getMax());
}
}

Time Complexity: The time complexity is O(1) as for the maximum element, we just have to peek at the top element of the max_stack.

Space Complexity (Auxiliary Space): The space complexity is O(N) as we have taken an auxiliary array to keep the track of the maximum element of the stack.

We tried to discuss Tracking the Current Maximum Element in the Stack. We hope this article gives you a better understanding of Tracking the Current Maximum Element in the Stack, PrepBytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program which will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.