Solution Explanation:

This problem requires designing a data structure, MaxStack, that efficiently handles stack operations (push, pop, top) and operations related to finding and removing the maximum element (peekMax, popMax). The challenge is to achieve O(1) time complexity for top and O(log n) for other operations. A naive stack implementation would fail to meet this requirement for popMax, which would take O(n) in the worst case.

Approach: Using a Doubly Linked List and a Sorted Set (Python, Java) or a Multimap and a List (C++)

The optimal solution uses two data structures in tandem to achieve the desired time complexities:

1. Doubly Linked List: This structure is used to maintain the order of elements as they are pushed and popped onto the stack, enabling O(1) access to the top element (top) and efficient removal of elements (pop).

2. Sorted Set (Python, Java) or Multimap (C++): This stores the nodes of the doubly linked list, sorted by their values. This facilitates O(log n) access to the maximum element (peekMax) and O(log n) removal of the maximum element (popMax). The Python and Java solutions use a SortedList and TreeMap respectively, which provide the necessary functionality. The C++ version uses a multimap to store the values and iterators pointing to their positions within the list, enabling O(log n) for all the operations.

Code Breakdown (Python Example):

The Python code utilizes the SortedList from the sortedcontainers library (you'll need to install it: pip install sortedcontainers).

• Node class: Represents a node in the doubly linked list, containing the value and pointers to the previous and next nodes.

• DoubleLinkedList class: Implements a basic doubly linked list for efficient stack operations.

• MaxStack class: The core class, containing the doubly linked list (stk) and the sorted set (sl).

  • push(x): Appends x to the doubly linked list and adds the corresponding node to the sorted set.
  • pop(): Removes the last node from the doubly linked list and removes the corresponding node from the sorted set.
  • top(): Returns the value of the last node in the doubly linked list.
  • peekMax(): Returns the value of the last node in the sorted set (the maximum value).
  • popMax(): Removes the last node (maximum value) from the sorted set, then removes the corresponding node from the doubly linked list.

The Java and C++ versions achieve similar functionality using their respective data structures. The C++ solution uses a multimap to efficiently track elements and their positions within the list, making operations like popMax very efficient.

Time and Space Complexity Analysis

• Time Complexity:

  • push(x): O(log n) – insertion into the sorted set.
  • pop(): O(log n) – removal from the sorted set.
  • top(): O(1) – direct access to the last node in the doubly linked list.
  • peekMax(): O(1) – direct access to the last element in the sorted set.
  • popMax(): O(log n) – removal from the sorted set and doubly linked list.

• Space Complexity: O(n) – to store the elements in both the doubly linked list and the sorted set.

Note

The choice of sorted set implementation might vary slightly depending on the programming language. The important aspect is that it provides logarithmic time complexity for insertion, deletion, and access to the maximum element. The doubly linked list ensures efficient stack operations. This combined approach optimally solves the problem's requirements.