GATE CS 2025 Set 2 — Question 45
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MSQ+2 / -0MediumStack OperationsStacks & QueuesProgramming & Data Structures
Programming & Data Structures → Stacks & Queues → Stack Operations
Last updated
Question
Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct.We wish to augment the stack data structure with an time MIN operation that returns a pointer to the record with smallest key present in the stack
1) without deleting the corresponding record, and
2) without increasing the complexities of the standard stack operations.Which one or more of the following approach(es) can achieve it?
1) without deleting the corresponding record, and
2) without increasing the complexities of the standard stack operations.Which one or more of the following approach(es) can achieve it?
Correct answer
(A) Keep with every record in the stack, a pointer to the record with the smallest key below it.
Solution
The problem requires adding a MIN operation to a stack with time complexity, without increasing the time complexity of PUSH and POP operations.Analysis of Options:
- (A) Keep with every record in the stack, a pointer to the record with the smallest key below it: This is the correct approach. By storing a pointer to the minimum element of the sub-stack below the current element, we can determine the minimum of the entire stack at any point in time. Specifically, if the current top element is , the minimum of the stack is . When pushing a new element, we can compute its "min below" pointer in using the current top's information. This maintains for PUSH, POP, and MIN.
- (B) Keep a pointer to the record with the smallest key in the stack: While this allows access to the minimum, if the minimum element is POPped, finding the next minimum would require scanning the remaining stack, taking time. This violates condition 2.
- (C) Keep an auxiliary sorted array: Inserting a new element into a sorted array takes time, which increases the complexity of the PUSH operation. This violates condition 2.
- (D) Keep a Min-Heap: Heap operations (insert, delete) take time. This increases the complexity of PUSH and POP operations. This violates condition 2.
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Stacks & Queues
2026 Set 2 Q12The set T represents various traversals over binary tree. The set S represents the order of…2026 Set 2 Q19Consider the following three ANSI-C programs, P1, P2, and P3. P1 [code] P2 [code] **P3**…2026 Set 1 Q23Let be an odd number greater than 100. Consider a binary minheap with elements stored in an…2026 Set 1 Q24Consider a hash table that is initially empty. The hash table is maintained…2026 Set 1 Q27Consider the following C statements: Which of the following options is/are correct? [figure]