Search Algoritm – Monotonic Stack technique

Introduction

Question such as finding next greater value in an array, stack could be used. Although we can use brute force, often implemented by double for loop, to traverse an array and find suitable value in O(n^2) time complexity, monotonic stack can help to achieve O(n) time. This blog explains monotonic stack technique and justifies how it helps reduce time complexity.

Concepts

Stack is FIFO data structure with 2 mains operation push and pop. Each has time complexity of O(1). If we push and pop an entire array to stack, then the total operations is 2n, and time complexity is O(n).

Monotonic Stack are stacks that store underlying increasing or decreasing value. Note that the values on the stack could be just indexes, pointers to values that are increasing or decreasing.

Problem final prices with special discount

The problem Final Prices With a Special Discount in a Shop could be solved with brute force using double for loop, as such each item will be accessed twice:

• first time when it is being picked as first item sell. The first for loop will loop through those items.
• second time when it is being picked as second item to be used as discount. The inner for loop will loop through all items after the first item.

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        vector<int>result;
        for(int i=0; i< prices.size();i++){
            for (int j=i+1; j< prices.size(); j++){
                if (prices[j] <= prices[i]){
                    result.push_back(prices[i]-prices[j]);
                    break;
                }
                else if( j >= prices.size()-1) result.push_back(prices[i]);
            }
        }
        result.push_back(prices[prices.size()-1]);
        return result;
    }
};

With monotonic stack technique, instead of looping again the same prices array, we use a stack to:

• store the items that has no discount yet by comparing the item of prices array with the stack's top, and push in the prices is higher.
• by the nature of the comparison, the item pushed into the stack will be increasing in value.

In addition, instead of pushing in prices[i] we can push the index i. Therefore:

• if the prices[i] > prices[stack.top()], update the result with result[prices[stack.top()]. That means we undated anywhere in the result array using the index values, stored in and pop out of the stack. Therefore, the actual time complexity is O(1) for such update.
• Although we use a while loop, understand that this while loop doesn't perform 1 update after looping through multiple items in its stack. Instead, multiple updates could be performed. If there are 4 items in the stack and the condition applies, then 4 updates on the result vector can be done! The is why we have O(1) complexity.

class Solution {
    public:
        vector<int> finalPrices(vector<int> & prices){
            stack<int> noDiscountYet;
            vector<int> result = prices;
            for (int i=0 ; i< prices.size(); i++){
                while(!noDiscountYet.empty() && prices[i] <= prices[noDiscountYet.top()]){
                    result[noDiscountYet.top()] -= prices[i];   
                    noDiscountYet.pop();
                }   // the while loop has time complexity of O(1)
                noDiscountYet.push(i);
            }
            return result;
        }
};