'Coding has over 700 languages', '67% of programming jobs aren’t in the
technology industry', 'Coding is behind almost everything that is powered
by electricity'

Problem of the day

Last Updated: 25 Dec, 2020

Easy

```
specialPush(value): should push the value in the stack in O(1).
specialPop( ) : should pop the last element from the stack in O(1).
specialTop( ): should give the element at the top of the stack in O(1).
specialMax( ): should give the maximum element from all the elements that are currently present in the stack in O(1).
```

```
Four types of queries denote these operations:
Type 1 : for specialPush(value) operation.
Type 2 : for specialPop( ) operation.
Type 3 : for specialTop( ) operation.
Type 4 : for specialMax( ) operation.
```

```
The first line of input contains a single integer 'Q', denoting the number of queries.
The next 'Q' line contains one operation per line.
Each operation starts with a single positive integer representing the type of operation.
If it is 1 then the operation is of type 1 and it is followed by a positive integer value.
If it is 2, 3, or 4 then it represents the operation of type 2, 3, and 4 respectively.
```

```
For each operation of type 2, return an integer on a single line - the element popped from the stack, and if there is underflow i.e. there is no element in the stack then return -1.
For each operation of type 3, return an integer on a single line - the top element of the stack and if the stack is empty return -1.
For each operation of type 4, return an integer on a single line - the maximum element on the stack and if the stack is empty return -1.
```

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= Q <= 10^6
1 <= type <= 4
1 <= value <= 10^9
Time Limit : 1 sec
```

- We will use two stacks, one is the normal stack to perform normal stack operations and the other one is the max stack to perform max stack operations.
- The key observation here is that we can store the element in the max stack only if it is greater than all the previous elements. This means the max stack has elements in ascending order.
- Because of this, the current top in the max stack will be the biggest element in the normal stack.
- So let’s see how we will implement the given functions.
- Type 1 : specialPush('VALUE') operation
- Push the ‘VALUE’ in the normal stack.
- Push the ‘VALUE’ in the max stack if it is empty or if the top is less or equal to ‘VALUE’.

- Type 2: specialPop( ) operation
- Pop the max stack if the top in the normal stack is equal to the top in the max stack.
- Pop the normal stack.
- Return the popped element.

- Type 3 : specialTop( ) operation
- Return the top of the normal stack.

- Type 4 : specialMax( ) operation
- Return the top of the max stack.

- For example in the first test case that is :
- 10
- 1 5 // Stack.specialPush(5)
- 1 4 // Stack.specialPush(4)
- 1 6 // Stack.specialPush(6)
- 1 1 // Stack.specialPush(1)
- 3 // Stack.specialTop()
- 4 // Stack.specialMax()
- 2 // Stack.specialPop()
- 2 // Stack.specialPop()
- 3 // Stack.specialTop()
- 4 // Stack.specialMax()

Similar problems

Postorder Traversal

Easy

Posted: 20 Jan, 2022

Postorder Traversal

Easy

Posted: 20 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Stock Span

Moderate

Posted: 16 Jun, 2022

Hills and Soldier

Moderate

Posted: 7 Jul, 2022

Hills and Soldier

Moderate

Posted: 7 Jul, 2022

Hills and Soldier

Moderate

Posted: 7 Jul, 2022

Hills and Soldier

Moderate

Posted: 7 Jul, 2022

Next Greater Element II

Moderate

Posted: 9 Sep, 2022