Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# 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:

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# 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: