Design a stack that supports getMin() in O(1) time and O(1) extra space
Implement a SpecialStack Data Structure that supports getMin() in O(1) time and O(1) extra space along with push(), pop(), top(), isEmpty(), isFull() in O(1). To implement SpecialStack, you should only use inbuilt Stack data structure.

Implement the following public functions :

1. push(data) : This function should take one argument of type integer. It pushes the element into the stack and returns nothing. 2. pop() : It pops the element from the top of the stack and, in turn, returns the element being popped or deleted. In case the stack is empty, it returns -1. 3. top() : It returns the element being kept at the top of the stack. In case the stack is empty, it returns -1. 4. isEmpty() : It returns a boolean value indicating whether the stack is empty or not. 5. getMin() : It returns the smallest element present in the stack. In case the stack is empty, it returns -1.

Operations Performed on the Stack:

Query-1(Denoted by an integer 1): Pushes integer data to the stack. (push function) Query-2(Denoted by an integer 2): Pops the data kept at the top of the stack and returns it to the caller. (pop function) Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the top of the stack but doesn't remove it, unlike the pop function. (top function) Query-4(Denoted by an integer 4): Returns a boolean value denoting whether the stack is empty or not. (isEmpty function) Query-5(Denoted by an integer 5): Returns the smallest element present in the stack. (getMin() function)

Input Format:

The first line contains an integer 'Q’, which denotes the number of queries to be run against each operation in the stack. The next 'Q' lines represent an operation that needs to be performed. For the push operation, the input line will contain two integers separated by a single space, representing the type of the operation in the integer and the integer data being pushed into the stack. For the rest of the operations on the stack, the input line will contain only one integer value, representing the query being performed on the stack.

Output Format:

For Query-1, you do not need to return anything. For Query-2, prints the data being popped from the stack. For Query-3, print the data kept on the top of the stack. For Query-4, print 'TRUE' or 'FALSE'(without quotes). For Query-5, print the smallest element present in the stack. Output for every query will be printed in a separate line.

Note:

You are not required to print anything explicitly. It has already been taken care of. Just implement the function.

Constraints:

1

Question

Design a stack that supports getMin() in O(1) time and O(1) extra space

Implement a SpecialStack Data Structure that supports getMin() in O(1) time and O(1) extra space along with push(), pop(), top(), isEmpty(), isFull() in O(1). To implement SpecialStack, you should only use inbuilt Stack data structure.

Implement the following public functions :

1. push(data) :
This function should take one argument of type integer. It pushes the element into the stack and returns nothing.

2. pop() :
It pops the element from the top of the stack and, in turn, returns the element being popped or deleted. In case the stack is empty, it returns -1.

3. top() :
It returns the element being kept at the top of the stack. In case the stack is empty, it returns -1.

4. isEmpty() :
It returns a boolean value indicating whether the stack is empty or not.

5. getMin() :
It returns the smallest element present in the stack. In case the stack is empty, it returns -1.

Operations Performed on the Stack:

Query-1(Denoted by an integer 1): Pushes integer data to the stack. (push function)

Query-2(Denoted by an integer 2): Pops the data kept at the top of the stack and returns it to the caller. (pop function)

Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the top of the stack but doesn't remove it, unlike the pop function. (top function)

Query-4(Denoted by an integer 4): Returns a boolean value denoting whether the stack is empty or not. (isEmpty function)

Query-5(Denoted by an integer 5): Returns the smallest element present in the stack. (getMin() function)

Input Format:

The first line contains an integer 'Q’, which denotes the number of queries to be run against each operation in the stack. 

The next 'Q' lines represent an operation that needs to be performed.

For the push operation, the input line will contain two integers separated by a single space, representing the type of the operation in the integer and the integer data being pushed into the stack.

For the rest of the operations on the stack, the input line will contain only one integer value, representing the query being performed on the stack.

Output Format:

For Query-1, you do not need to return anything.

For Query-2, prints the data being popped from the stack.

For Query-3, print the data kept on the top of the stack.

For Query-4, print 'TRUE' or 'FALSE'(without quotes).

For Query-5, print the smallest element present in the stack.

Output for every query will be printed in a separate line.

Note:

You are not required to print anything explicitly. It has already been taken care of. Just implement the function.

Constraints:

1 <= Q <= 1000
1 <= query type <= 5
-10^9 <= data <= 10^9 and data != -1

Where 'Q' is the total number of queries being performed on the stack and 'data' represents the integer pushed into the stack.

Time Limit: 1 sec

Accepted Answer

1. Start from brute force approach by using another stack.
2. Optimise it with reducing push and pop operations.
3. Optimise it to O(1) space complexity.

Accepted Answer

Optimal Solution

You need to make two separate stacks for solving the problem.
The first stack would have the actual number and the second stack would contain the minimum number present in the current stack.
Now, when we need to push a number in the stack, we first need to check if the stack is empty or not. If the stack is empty, we simply push the integer in both the stacks. Otherwise, we push the integer in the first stack and take the minimum of the top of the second stack and the current number and push it in the second stack.
For ‘POP’, we need to check if the stack is empty. If the stack is empty, we return ‘-1’. Otherwise, we first save the top of the first stack and pop it. Finally, we return it.
For ‘TOP’, we need to check if the stack is empty. If the stack is empty, we return ‘-1’. Otherwise, we return the top of the first stack.
For ‘GETMIN’, we need to check if the stack is empty. If the stack is empty, we return ‘-1’. Otherwise, we return the top of the second stack.
For ‘ISEMPTY’, we just need to check if the stack is empty.

Space Complexity: O(1)Explanation:

O(1)

Constant extra space is required.

Time Complexity: O(1)Explanation:

O(1)

For push(): O(1) - Constant extra space is required.

For pop(): O(1) - Constant extra space is required.
For top(): O(1) - Constant extra space is required.
For getMin(): O(1) - Constant extra space is required.
For isEmpty(): O(1) - Constant extra space is required.

Accepted Answer

Efficient Solution

You need to make two separate stacks for solving the problem.
The first stack would have the actual number and the second stack would contain the minimum number present in the current stack.
There is a modification in this approach, that the second stack(for maintaining minimum elements) would only push an element if it is less than or equal to the element at its top. This would help us reduce the space complexity(although in the worst case it would remain the same).
Now, when we need to push a number in the stack, we first need to check if the stack is empty or not. If the stack is empty, we simply push the integer in both the stacks. Otherwise, we push the integer in the first stack and take the minimum of the top of the second stack and the current number and push it in the second stack.
For ‘POP’, we need to check if the stack is empty. If the stack is empty, we return ‘-1’. Otherwise, we first save the top of the first stack and pop it. Finally, we return it.
For ‘TOP’, we need to check if the stack is empty. If the stack is empty, we return ‘-1’. Otherwise, we return the top of the first stack.
For ‘GETMIN’, we need to check if the stack is empty. If the stack is empty, we return ‘-1’. Otherwise, we return the top of the second stack.
For ‘ISEMPTY’, we just need to check if the stack is empty.

Space Complexity: O(1)Explanation:

O(1)

Constant extra space is required.

Time Complexity: O(1)Explanation:

O(1)

For pop(): O(1) - Constant extra space is required.
For top(): O(1) - Constant extra space is required.
For getMin(): O(1) - Constant extra space is required.
For isEmpty(): O(1) - Constant extra space is required.

Accepted Answer

Space Efficient Solution

We can store the minimum element encountered at any point of time in a variable, say ‘MINELE’.
To handle the case when the minimum element is removed, we would need to store the previous minimum element.
This can be done by storing the value 2 * 'DATA' - ‘MINELE’ when a new minimum value is added to the stack.
Now, when we need to push a number in the stack, we first need to check if the stack is empty or not. If the stack is empty, we simply push the integer in the stack and make the ‘MINELE’ as ‘DATA’. Otherwise, if the data is greater than or equal to the top value of the stack, simply push the data into the stack. Else, push 2 * 'DATA' - ‘MINELE’ in the stack and update the value of ‘MINELE’ as data.
For ‘POP’, we need to check if the stack is empty. If the stack is empty, we return ‘-1’. Otherwise, if the top value of the stack is greater than or equal to the ‘MINELE’ of the stack, simply pop the top value of the stack, the minimum value here would remain the same. Else, the top is the minimum element and hence we need to retrieve the previous minimum element in the stack. So update the ‘MINELE’ = 2 * ‘MINELE’ - ‘TOP’.
For ‘TOP’, we need to check if the stack is empty. If the stack is empty, we return ‘-1’. Otherwise, if the top value of the stack is greater than or equal to the ‘MINELE’ of the stack, simply return the top value of the stack. Else we need to return the minimum value in the stack, ‘MINELE’.
For ‘GETMIN’, we need to check if the stack is empty. If the stack is empty, we return ‘-1’. Otherwise, we return the minimum value in the stack, ‘MINELE’.
For ‘ISEMPTY’, we just need to check if the stack is empty.

Space Complexity: O(1)Explanation:

O(1)

Constant extra space is required.

Time Complexity: O(1)Explanation:

O(1)

For push(): O(1) - Constant extra space is required.

For pop(): O(1) - Constant extra space is required.
For top(): O(1) - Constant extra space is required.
For getMin(): O(1) - Constant extra space is required.
For isEmpty(): O(1) - Constant extra space is required.

Implement a SpecialStack Data Structure that supports getMin() in O(1) time and O(1) extra space along with push(), pop(), top(), isEmpty(), isFull() in O(1). To implement SpecialStack, you should only use inbuilt Stack data structure.

Implement the following public functions :

Operations Performed on the Stack:

Input Format:

Output Format:

Note:

Constraints:

Top Paytm Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Paytm Software Engineer