Which approach achieves O(1) MIN on a stack in GATE CS 2025 Set-2 Q44?

Option A is correct. Storing with every record a pointer to the minimum key below it ensures that MIN is always O(1) — just look at the top record's min-pointer. PUSH remains O(1) by comparing the new key with the current min and storing the appropriate pointer. POP is also O(1) since removing the top record restores the min-pointer of the new top automatically.

Why does Option B (single global min-pointer) not work for O(1) MIN stack?

A single global pointer works for PUSH and MIN, but fails during POP. If the minimum element is popped, the pointer becomes invalid and finding the next minimum requires scanning the entire stack — making POP O(n) in the worst case, not O(1).

Why is Option C (sorted auxiliary array) incorrect for O(1) MIN stack?

Maintaining a sorted array requires inserting elements in sorted order during PUSH, which takes O(n) time due to shifting. This increases PUSH complexity from O(1) to O(n), violating the requirement.

Why is Option D (Min-Heap) incorrect for O(1) MIN stack?

Min-Heap insertion (PUSH equivalent) takes O(log n) time, not O(1). This increases the PUSH complexity beyond the allowed O(1), making Option D unsuitable.

Stack with O(1) MIN Operation | GATE CS 2025 Set-2 Q44 Data Structures

Computer Sciences > GATE 2025 SET-2 > Stack Operations

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?

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

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

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

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

Correct : a

The correct answer is Option A.
The goal is to support O(1) MIN without slowing down PUSH or POP. Let''s check each approach.
Option A - Store a min-pointer with every record: When a new element is pushed, compare it with the current top''s min-pointer and store whichever is smaller alongside the new record. MIN is O(1) - just read the top record''s min-pointer. PUSH and POP remain O(1). This works perfectly and is correct.
Option B - Single global min-pointer: Works for PUSH and MIN, but fails for POP. If the minimum element is popped, the pointer becomes stale and finding the new minimum requires a full scan - making POP O(n). Incorrect.
Option C - Sorted auxiliary array: Inserting into a sorted array during PUSH requires O(n) time for shifting. This violates the O(1) PUSH requirement. Incorrect.
Option D - Min-Heap: Heap insertion takes O(log n), not O(1). PUSH complexity increases. Incorrect.
Option A is the classic and correct approach — it essentially maintains a "running minimum" at every level of the stack, so no matter what gets popped, the new top always knows the current minimum instantly.

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev