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
Which one or more of the following approach(es) can achieve it?
Solution :
The correct option is: Keep with every record in the stack, a pointer to the record with the smallest key below it.
To understand why this approach is correct and meets all the constraints, let's analyze the requirements and how each stack operation (, , and ) behaves under this scheme.
1. Analyzing the Proposed Approach:
When we push a record onto the stack, we store along with it a pointer. This pointer points to the record in the stack (at or below the current record) that has the minimum key.
2. How standard operations are implemented in time:
Let be the new record we want to push onto the stack, and let be the current top record of the stack before the push.
For a operation:
- If the stack is currently empty, the minimum record in the stack is itself. We set 's minimum pointer to point to .
- If the stack is not empty, the minimum element below is already tracked by the top record 's minimum pointer. Let this record be .
- We compare the key of with the key of .
- If , then is the new minimum, so we set .
- Otherwise, remains the minimum, so we set .
Since this only requires a single comparison and pointer assignment, the operation takes time.
For a operation:
- We simply remove the top record from the stack.
- Since each record maintains its own independent pointer to the minimum element below it, removing the top record does not affect or invalidate the minimum pointers of any records remaining in the stack.
- Thus, the operation also takes time.
For the operation:
- To find the minimum key in the stack, we look at the top record of the stack, say , and return its minimum pointer: .
- This is a simple pointer retrieval, which executes in time without deleting any records.
3. Why other approaches fail to meet the constraints:
- Keeping a single pointer to the record with the smallest key in the stack: While and could be handled in , a operation that removes the minimum element would force us to search the entire stack to find the next minimum, taking time.
- Keeping an auxiliary sorted array or a Min-Heap: Maintaining these auxiliary structures requires updating them during and operations. Inserting or deleting from a sorted array takes time, and doing so in a Min-Heap takes time, both of which increase the complexity of standard stack operations beyond .
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.
Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.