Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

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.

```
{
"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.)

- 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 * 10^{9}, for all`i`

.

We have provided two solutions.

O(n^{2}).

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(n^{2}).

O(n).

We use two extra stacks and one extra vector to store values.

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).

```
/*
* 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;
}
```

O(n).

Each operation is performed in constant time and there are total `n`

operations.

O(n).

We use one extra stack and one extra vector to store values.

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).

```
/*
* 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:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

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

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.

```
{
"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.)

- 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 * 10^{9}, for all`i`

.

We have provided two solutions.

O(n^{2}).

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(n^{2}).

O(n).

We use two extra stacks and one extra vector to store values.

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).

```
/*
* 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;
}
```

O(n).

Each operation is performed in constant time and there are total `n`

operations.

O(n).

We use one extra stack and one extra vector to store values.

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).

```
/*
* 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:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart