Problem Explanation:

We are given historical price quotes of a stock and need to calculate the span of the stock. The span for a given day is defined as the maximum number of consecutive days (from that day going backwards) where the price of the stock is less than or equal to the price of that given day. To achieve this, we need to implement a class, StockSpanner, which will take in the stock price for each day and calculate the stock span.

An important point to note here is that we initiate our stock span count from 1 and not 0 as each day can stand on its own even if the previous day's stock price was higher.

Example:

Let's consider the example of the stock prices [100,80,60,70,60,75,85]:

• The span for the first day is 1 as there are no previous days to compare with.
• The 2nd day the price drops to 80, so the span is again 1 as we don't count days where the price was higher.
• The 3rd day, the price again drops, so the span is 1.
• The 4th day, the price increases to 70. But the previous day's price (60) is less than or equal to today's price, so the span is 2.
• The 5th, 6th and 7th day follows the same logic and their spans are 1, 4 and 6 respectively.

Solution approach:

The approach we are going to take here is to use a stack to store the stock prices along with their spans. We calculate the span by continuously popping the stack while the top of the stack is less than the current price, adding the span to a count and then pushing the current price along with the calculated span onto the stack.

Python Solution:

1
2python
3class StockSpanner:
4
5    def __init__(self):
6        self.stack = []
7
8    def next(self, price: int) -> int:
9        span = 1
10        while len(self.stack) != 0 and self.stack[-1][0] <= price:
11            span += self.stack[-1][1]
12            self.stack.pop()
13        self.stack.append((price, span))
14        return span

Java Solution:

1
2java
3public class StockSpanner {
4    private Stack<int[]> stack = new Stack<>();
5
6    public StockSpanner() {
7    }
8
9    public int next(int price) {
10        int span = 1;
11        while (!stack.isEmpty() && stack.peek()[0] <= price) {
12            span += stack.pop()[1];
13        }
14        stack.push(new int[]{price, span});
15        return span;
16    }
17}

JavaScript Solution:

1
2javascript
3class StockSpanner {
4    constructor() {
5        this.stack = []
6    }
7
8    next(price) {
9        let span = 1;
10        while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
11            span += this.stack.pop()[1];
12        }
13        this.stack.push([price, span]);
14        return span;
15    }
16}

C++ Solution:

1
2cpp
3class StockSpanner {
4public:
5    stack<pair<int, int>> stack;
6    StockSpanner() {
7    }
8
9    int next(int price) {
10        int span = 1;
11        while (!stack.empty() && stack.top().first <= price) {
12            span += stack.top().second;
13            stack.pop();
14        }
15        stack.push({price, span});
16        return span;
17    }
18};

C# Solution:

1
2csharp
3public class StockSpanner {
4    private Stack<(int, int)> stack;
5    public StockSpanner() {
6        stack = new Stack<(int, int)>();
7    }
8
9    public int next(int price) {
10        int span = 1;
11        while (stack.Count > 0 && stack.Peek().Item1 <= price) {
12            span += stack.Peek().Item2;
13            stack.Pop();
14        }
15        stack.Push((price, span));
16        return span;
17    }
18}

The proposed solutions use the stack data structure to keep track of the price- span pairs. These pairs are pushed onto the stack whenever we calculate a new span. While calculating the span for a price, we keep on popping from the stack till we find a price that is less than or equal to the current price. The spans of all such prices are added to get the span for the current price. The time complexity is O(N) as we add and remove all elements to and from the stack not more than once, where N is the number of price quotes.

We can summarize the solutions for different programming languages as follows:

1. Python: Python's list gives a simple interface for a stack through built-in functions like pop() for popping an element and -1 for getting the topmost element. A tuple is used to store each price-span pair in the stack.

2. Java: Java has a built-in Stack class which provides all stack-related functionalities like push(), pop(), and peek(). An array is used to store each price-span pair in the stack.

3. JavaScript: JavaScript's array provides stack functionalities like pop() and array[-1] for peeking. Each price-span pair is stored as an array inside the primary array serving as the stack.

4. C++: C++ uses the STL stack class for stack operations. A pair is used to store each price-span pair in the stack and is pushed and popped using push() and pop(). top() is used to peek the stack.

5. C#: C# uses the Stack class from the System.Collections.Generic namespace which provides stack functionalities via Pop(), Peek(), and Push(). Each price-span pair is stored as a tuple in the stack.