• The result of each method call will be part of the output sequence.
Goal: To implement the stack operations with constant time complexity.
Steps:
• Use a linked list node to store each element and the minimum element at that point in the stack.
• Each node should hold the current element and the minimum value up to that element.
• The push operation should update the minimum if the current element is smaller than the current minimum.
• The pop operation should simply remove the top node from the stack.
• The top operation should return the value of the top node.
• The getMin operation should return the minimum value stored in the top node.
Goal: The stack supports constant-time operations for each function.
Steps:
• Each function should operate in O(1) time complexity.
Assumptions:
• The stack is non-empty when pop, top, and getMin are called.
• Input: [[], [-2], [0], [-3], [], [], [], []]
• Explanation: This series of operations initializes the MinStack and performs various operations on it. The stack changes as elements are pushed and popped, and getMin returns the current minimum element after each operation.
Approach: A linked list approach is used where each node holds the element and the minimum value up to that point in the stack. This allows constant-time retrieval of the minimum element.
Observations:
• The stack needs to support constant-time retrieval of the minimum element.
• Each node should store the current minimum value to achieve O(1) retrieval time for getMin.
Steps:
• Create a Node class that stores the current value, the minimum value up to that point, and a reference to the next node.
• The push method creates a new node and assigns it a minimum value that is the lesser of the current element and the minimum value in the previous node.
• The pop method removes the top node from the stack.
• The top method returns the value of the top node.
• The getMin method returns the minimum value from the top node.
Empty Inputs:
• The stack will never be empty when pop, top, or getMin are called.
Large Inputs:
• The solution must efficiently handle up to 30,000 operations.
Special Values:
• Handle large and negative values for stack elements.
Constraints:
• Each operation must run in O(1) time.
int val;
int mn;
Node* node;
Node(int val, int mn, Node* node) {
this->val = val;
this->mn = mn;
this->node = node;
}
};
classMinStack {
public:Node* head;
MinStack() {
head =NULL;
}
voidpush(int val) {
if(!head) {
head =new Node(val, val, NULL);
} else {
head =new Node(val, min(head->mn, val), head);
}
}
voidpop() {
head = head->node;
}
inttop() {
return head->val;
}
intgetMin() {
return head->mn;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
1 : Variable Declaration
int val;
Declare an integer 'val' to store the current value pushed to the stack.
2 : Variable Declaration
int mn;
Declare an integer 'mn' to store the minimum value in the stack at the current point.
3 : Pointer Declaration
Node* node;
Declare a pointer 'node' that will point to the next node in the linked list.
4 : Constructor
Node(int val, int mn, Node* node) {
Constructor for Node which initializes 'val', 'mn', and 'node' fields.
5 : Constructor Initialization
this->val = val;
Set the value 'val' of the current node.
6 : Constructor Initialization
this->mn = mn;
Set the minimum value 'mn' of the current node.
7 : Constructor Initialization
this->node = node;
Set the 'node' pointer to point to the next node in the stack.
8 : Class Declaration
classMinStack {
Define the MinStack class, which represents the stack with operations to push, pop, and retrieve minimum values.
9 : Pointer Declaration
Node* head;
Declare a pointer 'head' to the top node of the stack.
10 : Constructor
MinStack() {
Constructor for MinStack class, initializing the stack.
11 : Initialization
head =NULL;
Initialize the 'head' pointer to NULL, indicating the stack is empty.
12 : Function Definition
voidpush(int val) {
Define the push function to add a new element to the stack.
13 : Conditional Check
if(!head) {
Check if the stack is empty (head is NULL).
14 : Node Creation
head =new Node(val, val, NULL);
Create a new node with the value 'val', setting its minimum to 'val' and pointing to NULL.
15 : Else Block
} else {
Else block executed when the stack is not empty.
16 : Node Creation
head =new Node(val, min(head->mn, val), head);
Create a new node with the value 'val', updating the minimum to be the smaller of the current minimum and 'val'.
17 : Function Definition
voidpop() {
Define the pop function to remove the top element from the stack.
18 : Pointer Update
head = head->node;
Update the 'head' pointer to point to the next node in the stack, effectively removing the current top node.
19 : Function Definition
inttop() {
Define the top function to return the value of the current top element of the stack.
20 : Return Statement
return head->val;
Return the value of the top node in the stack.
21 : Function Definition
intgetMin() {
Define the getMin function to retrieve the minimum value in the stack.
22 : Return Statement
return head->mn;
Return the minimum value of the top node in the stack.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: Each operation (push, pop, top, getMin) runs in constant time.
Best Case: O(1)
Worst Case: O(n)
Description: In the worst case, the space complexity is O(n) due to the linked list nodes storing each element in the stack.
