GATE 2025 CS (CS2) – Question 45
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 $O(1)$ 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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) Keep with every record in the stack, a pointer to the record with the smallest key below it.
Explanation
We need MIN to run in $O(1)$ time without making `PUSH` or `POP` slower.
- **(A) Works.** Store, with every record, a pointer to the minimum record at or below it in the stack. `PUSH` computes the new minimum from the previous top's pointer and the new key in $O(1)$; `POP` just discards the top record; `MIN` reads the top's pointer in $O(1)$.
- **(B) Does not work.** After popping the current minimum, you would need the next smallest key, which a single pointer does not provide without scanning the stack ($O(n)$).
- **(C) Does not work.** Inserting into a sorted array takes $O(n)$ (to shift elements).
- **(D) Does not work.** A min-heap makes `PUSH` and `POP` cost $O(\log n)$, which increases the cost of the standard stack operations. (Also, `POP` needs to remove an arbitrary element from the heap.)
Answer: A.