Skip to content
GATEiit

GATE CSE 2025 Session 2 Q45: Supporting an O(1) MIN operation on a stack

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

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: A (official GATE 2025 final answer key)

Concept used: A min-stack stores, with each entry, the minimum of everything below it, so POP restores the previous minimum in O(1)O(1).

First step: Ask what each approach must do after POP removes the current minimum, and what PUSH costs with a sorted array or a heap.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 2 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

More Programming and Data Structures PYQs

PracticePractise Programming and Data Structures questions →Full paperAll GATE CSE 2025 Session 2 questions →