GATE CS 2025 Set 2 | Question 45

MSQ · 2 marks

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?

  1. Option A: Keep with every record in the stack, a pointer to the record with the smallest key below it. (correct)
  2. Option B: Keep a pointer to the record with the smallest key in the stack.
  3. Option C: Keep an auxiliary array in which the key values of the records in the stack are maintained in sorted order.
  4. Option D: Keep a Min-Heap in which the key values of the records in the stack are maintained.

Answer

(A)

Explanation

  • A works. On PUSH, the new record stores a pointer to the minimum of the records below it: the smaller of the old top and the record the old top points to, found in \(O(1)\). MIN compares the top with the record its pointer names, also \(O(1)\). POP just removes the top, and the pointers in the records left behind are still correct.
  • B fails. Once the minimum is popped, finding the new minimum needs an \(O(n)\) scan, so POP gets slower.
  • C fails. Keeping an array sorted costs \(O(n)\) shifting on each PUSH and POP.
  • D fails. Heap insertion and deletion take \(O(\log n)\), so PUSH and POP are no longer \(O(1)\).

Answer: A