Discussion
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?
Answer: A
Only keeping, with every record, a pointer to the record with the smallest key below it works.
On PUSH, compare the new key with the minimum stored in the current top record and save a pointer to whichever is smaller (the new record itself if it is smaller): O(1). On POP, simply discard the top record; the record beneath already holds the minimum of everything below it. MIN reads the top record's pointer: O(1). No standard operation becomes slower.
A single pointer to the minimum fails when the minimum is popped: finding the new minimum then needs a scan of the stack, O(n). A sorted auxiliary array makes PUSH and POP O(n), since an element must be inserted or removed in the middle. A min-heap gives O(1) MIN but makes PUSH and POP O(log n), increasing their complexity.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development