Solution For Online Stock Span

Problem Statement:

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock’s price for the current day.
The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today’s price.

Example:

StockSpanner spanner = new StockSpanner();

spanner.next(100); // returns 1

spanner.next(80); // returns 1

spanner.next(60); // returns 1

spanner.next(70); // returns 2

spanner.next(60); // returns 1

spanner.next(75); // returns 4

spanner.next(85); // returns 6

Solution:

Approach: We can solve this problem using stack data structure. We will keep storing the stock prices in the stack and for every new stock, we will compare it with the topmost stock price in the stack. If the new stock price is greater than the topmost stock in the stack, then we will just pop the topmost stock until either the stack becomes empty or the topmost stock price is greater than current stock price. We will keep a count of the number of stocks popped from the stack and add it to the result.

Algorithm:

1. Keep two stacks of stock prices and stock span respectively.

2. For each new stock, calculate its span by comparing it with the last stock stored in the stack.

3. If the new stock price is greater than the last stock price, keep popping the stocks from the stack until either the stack becomes empty or the topmost stock price is greater than the current stock price.

4. Keep a count of the number of stocks popped and add it to the span of the current stock.

5. Push the current stock price and its span into the stacks.

6. Return the span of the current stock.

Code:

Below is the code implementation of the above-mentioned algorithm.

class StockSpanner {

Stack<Integer> prices;
Stack<Integer> spans;

public StockSpanner() {
    prices = new Stack<>();
    spans = new Stack<>();
}

public int next(int price) {
    int span = 1;

    while(!prices.isEmpty() && prices.peek() <= price) {
        prices.pop();
        span += spans.pop();
    }

    prices.push(price);
    spans.push(span);

    return span;
}

}

Time Complexity: The time complexity of the above algorithm is O(N) where N is the number of stock prices given as input. As we are iterating over the stack until it becomes empty or the topmost stock price is greater than the current stock price, in the worst case, we may have to iterate over the entire stack.

Space Complexity: The space complexity of the above algorithm is O(N) as we are using two stacks to store the stock prices and their respective span.

Step by Step Implementation For Online Stock Span

class StockSpanner {
    // use a stack to keep track of the previous days' stock prices
    // as well as the number of days since those prices
    Stack prices, weights;
    
    public StockSpanner() {
        prices = new Stack();
        weights = new Stack();
    }
    
    public int next(int price) {
        int w = 1;
        // as long as there are previous days' stock prices 
        // that are less than the current price, keep popping
        // them off the stack and adding their weights to w
        while (!prices.isEmpty() && prices.peek() <= price) {
            prices.pop();
            w += weights.pop();
        }
        // push the current price and weight onto the stack
        prices.push(price);
        weights.push(w);
        // return the weight
        return w;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

class StockSpanner:
    def __init__(self):
        self.stack = []
        
    def next(self, price: int) -> int:
        # This variable will keep track of how many days the current stock price has been greater than all the stock prices before it. 
        # We initialize it to 1 since the stock price is always greater than or equal to itself.
        span = 1
        
        # While there are still elements in the stack and the price of the current stock is greater than the price of the last stock in the stack
        while self.stack and self.stack[-1][0] <= price:
            # We pop the last element from the stack and add its span to the current span. 
            # This essentially means that the current stock spans all the days that the last stock spanned plus one more day.
            span += self.stack.pop()[1]
            
        # We push the current stock price and its span onto the stack
        self.stack.append((price, span))
        
        # We return the span of the current stock
        return span

var StockSpanner = function() {
    this.stocks = [];
};

/** 
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function(price) {
    // add the current price to our stocks array
    this.stocks.push(price);
    
    // set our counter for how many days the stock spans
    let counter = 1;
    
    // loop through the stocks array in reverse order
    // (since we're interested in the days the stock spans BACKWARDS)
    for (let i = this.stocks.length - 2; i >= 0; i--) {
        // if the stock at the current index is less than or equal to
        // the price we just added, increment our counter and continue
        // checking the next stock
        if (this.stocks[i] <= price) {
            counter++;
        } else {
            // if the stock at the current index is greater than the
            // price we just added, that means the current price spans
            // back counter days, so we can return counter and stop
            // checking any more stocks
            return counter;
        }
    }
    
    // if we get all the way through the loop without returning, that
    // means the current price spans the ENTIRE stocks array, so we
    // just return the length of the array
    return counter;
};

/** 
 * Your StockSpanner object will be instantiated and called as such:
 * var obj = new StockSpanner()
 * var param_1 = obj.next(price)
 */

class StockSpanner {
public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        int res = 1;
        while (!st.empty() && st.top().first <= price) {
            res += st.top().second;
            st.pop();
        }
        st.push({price, res});
        return res;
    }

private:
    stack> st;
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */

public class StockSpanner {
    Stack prices, weights;
    public StockSpanner() {
        prices = new Stack();
        weights = new Stack();
    }
    
    public int Next(int price) {
        int w = 1;
        while (!prices.isEmpty() && prices.peek() <= price) {
            prices.pop();
            w += weights.pop();
        }
        
        prices.push(price);
        weights.push(w);
        return w;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.Next(price);
 */