Question Details

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?

Options

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.

Show Answer
Correct Answer
A
Keep with every record in the stack, a pointer to the record with the smallest key below 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 (PUSH, POP, and MIN) 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 O(1) time:
Let R be the new record we want to push onto the stack, and let T be the current top record of the stack before the push.

For a PUSH(R) operation:
- If the stack is currently empty, the minimum record in the stack is R itself. We set R's minimum pointer to point to R.
- If the stack is not empty, the minimum element below R is already tracked by the top record T's minimum pointer. Let this record be M=T→min_ptr.
- We compare the key of R with the key of M.
- If key(R)<key(M), then R is the new minimum, so we set R→min_ptr=R.
- Otherwise, M remains the minimum, so we set R→min_ptr=M.
Since this only requires a single comparison and pointer assignment, the PUSH operation takes O(1) time.

For a POP() 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 POP operation also takes O(1) time.

For the MIN() operation:
- To find the minimum key in the stack, we look at the top record of the stack, say T, and return its minimum pointer: T→min_ptr.
- This is a simple pointer retrieval, which executes in O(1) 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 MIN and PUSH could be handled in O(1), a POP operation that removes the minimum element would force us to search the entire stack to find the next minimum, taking O(n) time.
- Keeping an auxiliary sorted array or a Min-Heap: Maintaining these auxiliary structures requires updating them during PUSH and POP operations. Inserting or deleting from a sorted array takes O(n) time, and doing so in a Min-Heap takes O(log n) time, both of which increase the complexity of standard stack operations beyond O(1).

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

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.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

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.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: