Implement a stack supporting max and popMax

Q: Implement a stack supporting max and popMax

This question evaluates understanding of data structures and algorithmic complexity, focusing on designing a stack variant that supports efficient retrieval and removal of the current maximum while preserving stack behavior.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Design a data structure that behaves like a stack but also supports retrieving and removing the current maximum value.

Implement a class MaxStack with the following operations:

push(x) : Push integer x onto the stack.
pop() : Remove and return the top element.
top() : Return the top element without removing it.
peekMax() : Return the maximum element currently in the stack without removing it.
popMax() : Remove and return the maximum element currently in the stack. If there are multiple occurrences of the maximum value, remove the one closest to the top of the stack.

All operations should be efficient (better than linear time when possible).

Implement a stack supporting max and popMax

Quick Overview

Comments (0)