GATE CS 2025 Set 2 Q35 — Arrays, Stacks and Queues

To achieve an $O(1)$ time complexity for the MIN operation without increasing the $O(1)$ time complexity of the standard stack operations (PUSH and POP), we must ensure that both insertions and deletions can update the minimum tracking information in $O(1)$ time.

Analyzing the Options:

• Option A: Keep with every record in the stack, a pointer to the record with the smallest key below it (including itself).
  • PUSH Operation: When pushing a new record $R$, we compare its key with the key of the minimum element of the stack prior to this push (which is pointed to by the previous top element's pointer). The minimum for $R$ is the smaller of the two. This requires only $O(1)$ time.
  • POP Operation: When popping the top element, we simply remove it. The next element below it already contains the correct pointer to the minimum of the remaining stack. No updates to other elements are needed, taking $O(1)$ time.
  • MIN Operation: We simply return the pointer stored in the current top element of the stack. This takes $O(1)$ time.
  Thus, Option A successfully achieves all requirements.


• Option B: Keep a single pointer to the record with the smallest key in the stack.
  • If the current minimum element is popped, we lose the reference to the next minimum element. To find the new minimum, we would have to scan the entire stack, which takes $O(n)$ time. This increases the complexity of the POP operation.


• Option C: Keep an auxiliary array in sorted order.
  • Maintaining a sorted array requires $O(n)$ time for insertion (during PUSH) or deletion (during POP) to shift elements. This increases the complexity of standard stack operations.


• Option D: Keep a Min-Heap.
  • Inserting into or deleting from a Min-Heap takes $O(\log n)$ time. This increases the complexity of PUSH and POP operations from $O(1)$ to $O(\log n)$.

Hence, only Option A satisfies all the given conditions.