GATE CSE 2025 | Set 2 | Question: 35

Question

​​​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?

• A. Keep with every record in the stack, a pointer to the record with the smallest key below it.
• B. Keep a pointer to the record with the smallest key in the stack.
• C. Keep an auxiliary array in which the key values of the records in the stack are maintained in sorted order.
• D. Keep a Min-Heap in which the key values of the records in the stack are maintained.

Answer 1

We had already solved the same question in 2023 and it was asked again in GATE 2025.

Watch this video to learn the most efficient and crystal-clear solution 👇

Watch GATE 2025 Stack Question
(on YouTube)

youtu.be/EfC7WxqB94E?t=4885

In fact, we had already asked similar questions in our Weekly Quizzes

• 🔹 Weekly Quiz 3 — Question 10 [PDF]

 

One slight variation:  🔹 Weekly Quiz 3 — Question 5 [PDF]

We made it popular long before GATE asked it for the first time 😎

Comments

😯

Answer 2

Answer: A only.

Why:

• A works: store with each node a pointer to the minimum element below it.

  • MIN: look at minBelow(top) and compare with top → O(1).

  • PUSH/POP: only the new/top node’s pointer needs setting; others are unaffected → still O(1).

• B fails: if the min gets popped, you’d need to rescan to find the next min → worse than O(1) POP.

• C fails: maintaining a sorted auxiliary array makes PUSH/POP O(n).

• D fails: updating a heap on every PUSH/POP is O(log n) (and removing arbitrary popped elements is worse without extra machinery).

So, only A achieves O(1) MIN without increasing stack operation complexities.

Answer 3

Option A
Each stack node stores: Its key. and A pointer to the previous minimum key in the stack.When a new element is pushed: If it is smaller than the current minimum, update its minimum pointer to itself. Otherwise, inherit the minimum pointer from the previous top. When popping: The previous minimum is restored automatically.

Comments

For finding min just follow the min_below pointer of the top.

---

the best explanation. the diagrams are speaking for themselves. thank you sir

 

Answer 4

Option A: Keep with every record, a pointer to the record with the smallest key below it.

This is a valid and efficient approach.

Each stack node stores a pointer to the record with the smallest key among all records below it (i.e., deeper in the stack).
When pushing a new element $x$:

• Compare $ x $’s key with the key of the current top’s “min_below” record.
• Set the new node’s “min_below” pointer to point to whichever has the smaller key (either the existing minimum below or $ x $ itself if it’s smaller but note, since $ x $ is on top, “below” means excluding $ x $).
• Then, to compute the global minimum for the MIN operation, compare the new top’s key with the key of the record pointed to by its “min_below” pointer and return the pointer to the smaller one. This is $ O(1) $.

When popping:

Simply remove the top. The new top already has its own precomputed “min_below” pointer no recomputation needed. Thus, PUSH, POP, and MIN all remain $ O(1) $.

$\text{Option A works}$

---

 

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

This is insufficient.

While we can update the pointer during PUSH (by comparing the new key with the current minimum), the problem arises during POP.

If the popped element is the current minimum, we must find the new minimum but scanning the stack takes $ O(n) $ time.

Without maintaining additional structure (like a stack of historical minimums), we cannot update the pointer in $ O(1) $ after such a POP.

$\text{Option B fails to guarantee} $ O(1) $ POP$

---

 

Option C: Keep an auxiliary array in sorted order.

To maintain sorted order, every PUSH requires finding the correct insertion position $ O(n) $ time.

Similarly, POP requires removing an element and shifting also $ O(n) $.

Although MIN (first element) is $ O(1) $, PUSH and POP are not.

$\therefore$ Violates the requirement of $ O(1) $ standard operations.

---

 

Option D: Keep a Min-Heap.

A Min-Heap can return the minimum in $ O(1) $, but insertion and deletion take $ O(\log n) $.

PUSH and POP would no longer be $ O(1) $.

$\therefore$ Violates the requirement.

 

Only  $\boxed{\text{Option A}}$  satisfies all constraints enabling $ O(1) $ MIN while preserving $ O(1) $ PUSH and POP.

Answer 5

✅ Correct Approaches

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

• Why it works: This is the textbook trick for O(1) MIN in a stack.

  • When you push a new record, compare its key with the current minimum (from the top record’s pointer).

  • Store a pointer to the smaller one.

  • On pop, the next record already knows the minimum below it.

• Time Complexity:

  • PUSH, POP, and MIN all stay O(1).

• Space Tradeoff:

  • Slight increase in space per record, but no extra data structures.

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

• Why it fails:

  • Works only for PUSH, but breaks on POP.

  • If the minimum record is popped, you lose track of the new minimum unless you scan the stack—O(n).

• Verdict: ❌ Not sufficient for guaranteed O(1) MIN.

❌ Incorrect Approaches

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

• Why it fails:

  • Maintaining sorted order on every PUSH or POP is O(log n) or worse.

  • Violates the constraint of not increasing standard stack operation complexity.

• Verdict: ❌ Too slow.

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

• Why it fails:

  • Min-Heap gives O(1) MIN, but PUSH and POP become O(log n).

  • Again, violates the constraint.

• Verdict: ❌ Not allowed.

🧠 Final Answer:

Only Option A is correct.