Design a stack that supports getMin() in O(1) time and O(1) extra space

Introduction

Stacks are fundamental data structures often utilized in computer science and software engineering. They use the Last-In-First-Out (LIFO) principle, which means that the most recently inserted piece is the first to be eliminated. Traditional stack solutions on the other hand need to get the minimum element efficiently. In this article, we will look at a creative approach for creating a stack that allows for constant retrieval of the smallest element while taking up no more space outside of the stack.

Understanding The Problem

The aim is to create a stack data structure that not only supports typical stack operations like push, pop, and peek but also efficiently supports retrieving the minimal element in constant time, i.e. O(1). Furthermore, we want to accomplish this without adding any additional space complexity, preserving O(1) extra space.

Operations

Push(x): This action adds element x to the top of the stack and guarantees that the stack's minimum element is properly updated.

Pop():This method removes the top element from the stack. If the top element is the minimal element, it should also be removed from the auxiliary stack.

Top(): This method retrieves the top member of the stack without deleting it.

getMin(): This method returns the lowest element presently on the stack.

Here is a detailed explanation of how each procedure works:

Push(x):

• Add the element x to the main stack.
• If the auxiliary stack is empty or x is less than or equal to the auxiliary stack's top element, push x onto it.
• Otherwise, copy the top element of the auxiliary stack and push it to the auxiliary stack.

Pop():

• Remove the top element from the main stack.
• If the popped element is the same as the auxiliary stack's top element, pop both.

Top():

• Return the top element from the main stack without deleting it.

getMin():

• Return the auxiliary stack's top element, which corresponds to the minimal element in the main stack.

The strategy for creating a stack that enables getMin() in O(1) time and O(1) additional space is making creative use of an auxiliary stack to keep track of the minimum element at each given primary stack state. Here's a step-by-step description of the approach:

Approach 1: The primary stack (or main stack):

• This stack retains the components that are placed onto it.
• It supports common stack operations, including push, pop, and peek.

Approach 2: Auxiliary stack (min stack):

• This stack complements the main stack.
• It keeps track of the lowest element present in the primary stack at any given time.
• When an element is placed into the primary stack, we compare it to the top element of the auxiliary stack.
• If the element is smaller than or equal to the top of the auxiliary stack, it is pushed onto it.
• If the element is bigger, we duplicate the top of the auxiliary stack by pushing it once more.
• It assures that the auxiliary stack always has the minimal element up to the primary stack's current state.

Implementation

Output:

Explanation

• In this approach, each stack node (StackNode) stores two bits of information: the data and the node's minimum value.
• If the stack is empty during the push() operation, the data is set as the new node's min value. Otherwise, it is set to the minimum of the current data plus the previous minimum value (top.min).
• The pop(), top(), and isEmpty() functions function normally for a stack implementation.
• The getMin() function returns the top node's minimal value with a retrieval time complexity of O(1).