SpecialStack Design Problem

Design a stack that efficiently supports the getMin() operation in O(1) time with O(1) extra space. This stack should include the following operations: push(), pop(), top(), isEmpty(), and getMin(), all with O(1) time complexity, using only the inbuilt stack data structure.

Your task is to implement a data structure that fulfills these requirements.

Input:

The first line provides an integer ‘Q’, indicating the number of queries to process. The following 'Q' lines represent the operations to perform on the stack. For a push operation, the line contains two integers: the operation type and the data to push. Other operations contain just an integer indicating the operation type.

Output:

For Query-1 (push), no output is required. For Query-2 (pop), output the popped data. For Query-3 (top), output the data top of the stack. For Query-4 (isEmpty), output 'TRUE' or 'FALSE'. For Query-5 (getMin), output the smallest element in the stack. Each query's output should be on a new line.

Example:

Input:
7
1 10
1 20
4
3
5
2
5
Output:
FALSE
20
10
20
10

Constraints:

  • 1 <= Q <= 1000
  • 1 <= query type <= 5
  • -109 <= data <= 109 and data != -1
Note:
The printing of results for each operation has been managed for you. Implement the required functionality in the designated functions.
AnswerBot
1d

Design a stack that supports getMin() operation in O(1) time with O(1) extra space using inbuilt stack data structure.

  • Use two stacks - one to store the actual data and another to store the minimum val...read more

Help your peers!
Add answer anonymously...
Paytm Software Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter