We wish to augment a stack with an O(1) MIN operation (returns pointer to min-key record, no deletio

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2025 GATE-CS Data Structures paper.

Q: How can I prepare for GATE-CS Data Structures?

To prepare for GATE-CS Data Structures, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2025 question covers Stacks topic.

Q: What is the difficulty level of this question?

This GATE-CS 2025 Data Structures question has a medium difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

We wish to augment a stack with an O(1) MIN operation (returns pointer to min-key record, no deletion, no increased push/pop complexity). Which approach(es) can achieve this?

Accepted Answer

Correct Answer: (A) onlyA — WORKS: Each record stores (key, min_so_far_pointer). On PUSH: compare new key with current top's min_so_far; set new record's min_so_far = whichever is smaller. MIN = return top's min_so_far. POP = standard. All operations O(1). ✓B — FAILS: Single pointer works only while min is never popped. On POP of the minimum, finding the new minimum requires O(n) scan. POP becomes O(n). ✗C — FAILS: Maintaining sorted order during PUSH requires O(n) insertion. PUSH becomes O(n). ✗D — FAILS: Min-Heap insertion/deletion is O(log n). PUSH and POP become O(log n). ✗

We wish to augment a stack with an O(1) MIN operation (returns pointer to min-key record, no deletion, no increased push/pop complexity). Which approach(es) can achieve this?

Master GATE-CS with Our Test Series

More Questions from Stacks

Frequently Asked Questions

We wish to augment a stack with an O(1) MIN operation (returns pointer to min-key record, no deletion, no increased push/pop complexity). Which approach(es) can achieve this?

Master GATE-CS with Our Test Series

More Questions from Stacks

Frequently Asked Questions