Largest Element in the Stack

Problem: Given a stack you have to insert a stream of numbers in it and you have to keep track of the highest element at any point in the stack

In general, the solution will require traversing through the entire stack hence taking O(n) time. However, given the option of using another data-structure this can be done using minimal extra memory using another "Stack" !.

The basic idea is when pushing an element in the original, check if the the "highest_elem_stack" is empty or if its top element is less than or equal to the element being pushed, if yes push this element on both stacks.

While popping check if the popped element is equal to the top element of the "highest_elem_stack". If yes pop both stacks.

The highest element in the original stack would always be equal to the top element in the "highest_elem_stack"