IAE Academy

GATE 2025 CS2 Q.45: solution and answer

GATE 2025 · CS2Q.45 · 2 marks · MSQ

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 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 approaches can achieve it?

  1. (A)

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

  2. (B)

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

  3. (C)

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

  4. (D)

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

See the question in the paper
GATE 2025 CS2 question 45Tap to open full size

Answer and solution

ANSWER

Only approach (A) — storing with every record a pointer to the smallest key below it — achieves an O(1) MIN operation without slowing down PUSH or POP; the correct option is (A) only.

Official answer: ASource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

  1. Requirement: PUSH and POP must stay O(1) (the standard stack complexities), and MIN must become O(1), without deleting/losing any record.

  2. (A) Augmented pointer per record: when a record is pushed, compare its key with the running minimum recorded at the (soon-to-be-previous) top; the new record stores a pointer to whichever is smaller (itself or that running minimum) as its own 'min-so-far' pointer. PUSH: O(1) — one comparison and one pointer write. POP: O(1) — simply discard the top; the record now exposed as the new top already carries the correct minimum for the reduced stack, computed at the time it was pushed. MIN: O(1) — read the pointer stored at the current top. No case increases the standard operations' complexity, so (A) works.

  3. (B) Single global min pointer: PUSH is still O(1) (update the pointer only if the new key is smaller). But POP fails when the popped record is the one the pointer references — the old minimum-before-that-push is nowhere recorded, so recovering the new minimum needs an O(n) scan of the remaining stack in the worst case. This increases POP's complexity, so (B) is rejected.

  4. (C) Auxiliary sorted array: inserting a new key at its correct sorted position requires shifting up to n array elements, making PUSH O(n) in the worst case; removing a specific (not necessarily top-of-array) key on POP similarly needs an O(n) search-and-shift. Both standard operations' complexities increase, so (C) is rejected.

  5. (D) Min-heap of keys: PUSH now requires a heap insertion, O(log n) rather than O(1). POP must remove the exact record being popped from the stack from the heap (not necessarily the heap's current minimum), which needs O(log n) with extra index bookkeeping rather than O(1). Both standard operations get slower than O(1), so (D) is rejected.

  6. Only (A) delivers O(1) MIN while leaving PUSH and POP at O(1); the answer is (A) only.

KEY IDEA

To add O(1) MIN to a stack without touching PUSH/POP's O(1) cost, the extra information must be attachable and readable in O(1) per operation and must never need to be recomputed from scratch on POP. Storing, with each element as it is pushed, a pointer to the minimum of everything below it achieves this because that stored value is fixed forever once written and POP never has to search for a replacement minimum — the newly exposed top already carries it.

WATCH OUT FOR

Thinking any structure that can report the minimum in O(1) is good enough, and overlooking that POP must also stay O(1): a single global min pointer (B) answers MIN in O(1) but forces an O(n) rescan on POP when the current minimum is popped, and a sorted array (C) or min-heap (D) cannot be kept updated in O(1) per PUSH/POP even though they can report the minimum quickly.

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 13 Linear structures questions, with notes

More Linear structures questions