GATE CS 2025 Set 2 Q.45: Stacks and Queues

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

without deleting the corresponding record, and
without increasing the complexities of the standard stack operations.

Which one or more of the following approach(es) can achieve it?

Keep with every record in the stack, a pointer to the record with the smallest key below it.

Keep a pointer to the record with the smallest key in the stack.

Keep an auxiliary array in which the key values of the records in the stack are maintained in sorted order.

Keep a Min-Heap in which the key values of the records in the stack are maintained.

Official answer and solution

Official answer: A
From: Official GATE 2025 answer key

Solution

Check which augmentation maintains $O(1)$ worst-case time for PUSH, POP, and MIN even when the minimum element is popped.

(A) is CORRECT: If every record $r$ $r$ in the stack stores a pointer to the minimum record among all elements below $r$ $r$ (or at/below $r$ $r$ ), then:
- MIN() compares the top record's key with the key pointed to by its min-pointer in $O(1)$ time.
- PUSH(x) sets x's min-pointer to the current stack minimum (found in $O(1)$ time via the old top record) in $O(1)$ time.
- POP() simply pops the top record in $O(1)$ time, and the new top record already stores the pointer to the minimum below it.
(B) fails: When the minimum record is popped, a single pointer cannot recover the next smallest element in $O(1)$ time (scanning the stack takes $\Theta(n)$ ).
(C) and (D) fail: Maintaining a sorted array takes $\Theta(n)$ per PUSH/POP, and maintaining a Min-Heap takes $O(\log n)$ per PUSH/POP, violating condition (2).

Final answer

Option (A)

Common trap

Selecting (B) without considering what happens when the minimum element is popped from the stack.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 45 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source