Implement A Min Stack Problem Statement
You have to build a min stack. Min stack should support push, pop methods (as usual stack) as well as one method that returns the minimum element in the entire stack.
You are given an integer array named operations of size n, containing values >= -1.
operations[i] = -1 means you have to perform a pop operation. The pop operation does not return the removed/popped element.operations[i] = 0 means you need to find the minimum element in the entire stack and add it at the end of the array to be returned.operations[i] >= 1 means you need to push operations[i] on the stack.
Example
{
"operations": [10, 5, 0, -1, 0, -1, 0]
}
Output:
[5, 10, -1]
Initially stack = [], ans = [].\
operations[0] = 10 -> push -> stack = [10], ans = []\
operations[1] = 5 -> push -> stack = [10, 5], ans = []\
operations[2] = 0 -> get minimum element -> stack = [10, 5], ans = [5]\
operations[3] = -1 -> pop -> stack = [10], ans = [5]\
operations[4] = 0 -> get minimum element -> stack = [10], ans = [5, 10]\
operations[5] = -1 -> pop -> stack = [], ans = [5, 10]\
operations[6] = 0 -> get minimum element -> stack = [], ans = [5, 10, -1] (As stack is empty we have to consider -1 as the minimum element.)
Notes
- Return an integer array
res, containing answer for each operations[i] = 0.
- If stack is empty, then do nothing for pop operation.
- If stack is empty, then consider -1 as the minimum element.
Constraints:
- 1 <=
n <= 100000
- -1 <=
operations[i] <= 2 * 109, for all i.
We have provided two solutions.
Implement A Min Stack Solution 1: Brute Force
Time Complexity
O(n2).
We transfer all elements of the stack while finding the minimum value; that takes O(n) time. There can be O(n) such queries for finding minimum values. O(n) * O(n) = O(n2).
Auxiliary Space Used
O(n).
We use two extra stacks and one extra vector to store values.
Space Complexity
O(n).
Space used for Input: O(n).
Auxiliary space used: O(n).
Space used for output: O(n).
Hence, O(n) + O(n) + O(n) = O(n).
Code For Implement A Min Stack Solution 1: Brute Force
/*
* Asymptotic complexity in terms of size of \`operations\` \`n\`:
* Time: O(n^2).
* Auxiliary space: O(n).
* Total space: O(n).
*/
vector<int> min_stack(vector<int> &operations)
{
vector<int> output;
stack<int> original, helper;
for (int operation : operations)
{
if (operation >= 1)
{
original.push(operation);
}
else if (operation == -1)
{
if (original.empty() == false)
{
original.pop();
}
}
else // operation == 0 so we must find the minimum element.
{
if (original.empty())
{
// If stack is empty, we must use -1.
output.push_back(-1);
}
else
{
// Find the minimum value by looking through all elements in the stack.
// As we pop elements, save them in the helper stack.
int min_val = 2000000000; // Biggest possible input value.
while (original.empty() == false)
{
min_val = min(min_val, original.top());
helper.push(original.top());
original.pop();
}
output.push_back(min_val);
// Now return all the elements back to the original stack.
while(helper.empty() == false)
{
original.push(helper.top());
helper.pop();
}
}
}
}
return output;
}
Implement A Min Stack Solution 2: Optimal
Time Complexity
O(n).
Each operation is performed in constant time and there are total n operations.
Auxiliary Space Used
O(n).
We use one extra stack and one extra vector to store values.
Space Complexity
O(n).
Space used for Input: O(n).
Auxiliary space used: O(n).
Space used for output: O(n).
Hence, O(n) + O(n) + O(n) = O(n).
Code For Implement A Min Stack Solution 2: Optimal
/*
* Asymptotic complexity in terms of size of \`operations\` \`n\`:
* Time: O(n).
* Auxiliary space: O(n).
* Total space: O(n).
*/
vector<int> min_stack(vector<int> &operations)
{
vector<int> output;
// At any point of time min_till_now.top() will contain minimum of all elements present in the stack.
stack<int> min_till_now;
for (int operation : operations)
{
if (operation >= 1)
{
int minimum_value = operation;
if (min_till_now.empty() == false)
{
minimum_value = min(minimum_value, min_till_now.top());
}
min_till_now.push(minimum_value);
}
else if (operation == -1)
{
if (min_till_now.empty() == false)
{
min_till_now.pop();
}
}
else // operation == 0 so we must find the minimum element.
{
if (min_till_now.empty())
{
// If stack is empty, we must use -1.
output.push_back(-1);
}
else
{
output.push_back(min_till_now.top());
}
}
}
return output;
}
We hope that these solutions to implement a min stack problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.
If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.
Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.
We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:
To learn more, register for the FREE webinar.
.png)
