Implement a Min Stack Problem - Interview Kickstart

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

Input: [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

Input Parameters: There is only one argument in input, denoting integer array named operations.

Output: Return an integer array res, containing answer for each operations[i] = 0.

Constraints:

• 1 <= n <= 100000

• -1 <= operations[i] <= 2 * 10^9, (i=0,1,...,n-1)

• If stack is empty, then do nothing for pop operation.

• If stack is empty, then consider -1 as the minimum element.

Solutions:

We have provided two solutions.

1) brute_force.cpp

Time Complexity:

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

Auxiliary Space Used:

O(n).

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

Space Complexity:

O(n).

Input is O(n).

Auxiliary space used is O(n).

Output is O(n).

Hence, O(n) + O(n) + O(n) -> O(n).


// -------- START --------
vector min_stack(vector operations)
{
    vector output;
    stack 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;
}
// -------- END --------

‍

2) optimal_solution.cpp

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

Input is O(n).

Auxiliary space used is O(n).

Output is O(n).

Hence, O(n) + O(n) + O(n) -> O(n).


// -------- START --------
vector min_stack(vector operations)
{
    vector output;
    // At any point of time min_till_now.top() will contain minimum of all elements present in the stack.
    stack 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;
}
// -------- END --------

‍