Hackerrank : Maximum Element

You have an empty sequence, and you will be given N queries. Each query is one of these three types:

1 x  -Push the element x into the stack.
2    -Delete the element present at the top of the stack.
3    -Print the maximum element in the stack.

Input Format

The first line of input contains an integer, N. The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)

1 <= N <= 10^5
1 <= x <= 10^9
1 <= type <= 3

Output Format

For each type  query, print the maximum element in the stack on a new line.

Sample Input

1 97
1 20
1 26
1 20
1 91

Sample Output


First thing you should notice is the constraint:
1 <= N <= 10^5
Most of the time, if you see the constraint is 10^5 (ten to the power of 5), it means your solution must be at most O(n log n) or better.

Okey, since it’s marked as “Easy” so there will be no hidden things that you need to figure out. Basically you need to build a stack and get the biggest elements in the stack and quick / fast as possible, so this is all about data structure.

Obviously we need a stack, to push and pop items as required. But how can we tell which item in the stack is biggest.

The easiest solution is go through the stack and get the max item. It works but it’s too slow. The time complexity will be O(n^2), roughly.

We can use an additional collection, like a Heap, more specifically, a MaxHeap to store the elements in order. To insert an item to a Heap, it is O(n log n), to remove an item in a heap, it’s aso O(n log n). Finally, this is what we want, to get the biggest element as fast as possible. Specifically for MaxHeap, the top will be the biggest element. Overall this will work and the time complexity will be roughly O(n log n). The hardest thing is to implement the MaxHeap yourself.

This is more “language-oriented”. It removes the “re-invent the wheel” part, no need to implement MaxHeap yourself.
In Java we have a SortedSet, it’s really fast for adding item as well as lookup smallest/largest item. The only problem though, is duplicated items. We need to watch out for duplicated items. Obviously, because set only stores non duplicated items. We can use a Map to store the item and its frequency. When the frequency goes down to 1, we know that we can remove the item from the set, as well as the frequency map. This is relatively fast, but it consumes a lot of spaces. It’s O(n) in space complexity.

This is when “algorithm” comes to handy. Let’s say we need to insert an item, and also we need to know what is the maximum value after we insert the new item. If this still isn’t enough for you then please continue reading. So instead of just saving an item, you can also save the max value so far given the new item, also we need a global max variable to know the max value so far. The item on the top of the stack is guaranteed to be paired with the biggest element. When the stack is empty we need to reset the maximum value and when popping item out of stack, we need to update the global max value (if needed).

There may be more solutions for this problem but these are what I’ve come up with.

Here’s the sample code if you get trouble implementing the mentioned solutions.