Consider a stack data structure into which we can PUSH and POP records. Assume…
2025
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 𝑂(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.
Attempted by 219 students.
Show answer & explanation
Correct answer: A
Suggested solution: Keep with every record in the stack a pointer to the record with the smallest key among that record and all records below it.
Push (O(1)): Create the new record. If the stack is empty, set the new record's min-pointer to itself. Otherwise compare the new record's key with the min key pointed to by the current top's min-pointer and set the new record's min-pointer to the record with the smaller key. Push the new record onto the stack.
Pop (O(1)): Remove the top record. No other updates are required because each remaining record already stores the correct min-pointer for the substack below it.
Min (O(1)): Return the min-pointer stored at the top record (or null if the stack is empty).
Complexity: PUSH, POP, and MIN all run in O(1) time. Extra space is one pointer per record (O(n)).
Why the other approaches fail:
Keeping only a single pointer to the current minimum: If the minimum element is popped, finding the new minimum requires scanning the stack (O(n)), so POP would not be O(1).
Maintaining an auxiliary array in sorted order: Inserting or deleting while preserving sorted order can take O(n) time, so PUSH and/or POP would not be O(1).
Using a min-heap: Heap insertions and deletions are O(log n). Also removing an arbitrary stack element from the heap (when POP removes a non-min element) requires locating and removing that element, which incurs extra overhead. Thus stack operations would not remain O(1).
A video solution is available for this question — log in and enroll to watch it.