Stock Span Problem Using Stack.

The stock span problem is a financial problem where we have a series of daily price quotes for a stock and we need to calculate the span of the stock's price for each day. The span of the stock's price for a particular day is defined as the maximum number of consecutive days (including the current day) for which the stock price is less than or equal to the price of the current day.

Example:

Input: [100, 80, 60, 70, 60, 75, 85]

Output: [1, 1, 1, 2, 1, 4, 6]

Explanation:

For day 1 (100), the span is 1, as it is the first day.
For day 2 (80), the span is 1, as the previous day's price (100) is greater.
For day 3 (60), the span is 1, as the previous day's price (80) is greater.
For day 4 (70), the span is 2, as the previous day's price (60) is smaller, so we include the day before that (60).
For day 5 (60), the span is 1, as the previous day's price (70) is greater.
For day 6 (75), the span is 4, as the previous day's price (60) is smaller, so we include the three days before that (60, 70, 60).
For day 7 (85), the span is 6, as the previous day's price (75) is smaller, so we include the five days before that (60, 70, 60, 75, 85).

There are many ways to solve this problem, popularly it is solved using stack or dynamic programming and here we are going to discuss all these approaches in detail starting with the brute force approach.

Stock Span Problem Using Brute Force Approach.

In this approach, for each day, we traverse backward and count the number of consecutive days with prices less than or equal to the current day's price. Traverse backward from i-1 to 0 and for each previous day j, compare the stock price at day i with the stock price at day j.

Below is the code implementation of the above approach:

C++ Java Python C#

// Cpp program for stock span problem (brute force)
#include <iostream>
#include <vector>
using namespace std;

vector<int> calculateSpan(const vector<int>& prices) {
    int n = prices.size();
    vector<int> span(n, 1);

    for (int i = 0; i < n; ++i) {
        int spanValue = 1;
         
        //traverse backwards and count the number of consecutive days 
        for (int j = i - 1; j >= 0 && prices[j] <= prices[i]; --j) {
            spanValue++;
        }

        span[i] = spanValue;
    }

    return span;
}

int main() {
    vector<int> stockPrices = {100, 80, 60, 70, 60, 75, 85};
    vector<int> span = calculateSpan(stockPrices);

    cout << "Stock Prices: ";
    for (int price : stockPrices) {
         cout << price << " ";
    }

    std::cout << "\nSpans: ";
    for (int s : span) {
        std::cout << s << " ";
    }

    return 0;
}

// Java program for stock span problem - brute force approach
import java.util.Arrays;

public class StockSpan {
    public static void main(String[] args) {
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        int[] span = calculateSpan(prices);

        System.out.println("Stock Prices: " + Arrays.toString(prices));
        System.out.println("Spans: " + Arrays.toString(span));
    }

    public static int[] calculateSpan(int[] prices) {
        int n = prices.length;
        int[] span = new int[n];
        Arrays.fill(span, 1);

        for (int i = 0; i < n; ++i) {
            int spanValue = 1;
            //traverse backwards and count the number of consecutive days
            for (int j = i - 1; j >= 0 && prices[j] <= prices[i]; --j) {
                spanValue++;
            }

            span[i] = spanValue;
        }

        return span;
    }
}

# Python program to solve stock span problem
def calculate_span(prices):
n = len(prices)
span = [1] * n

for i in range(1, n):
    span_value = 1

    for j in range(i - 1, -1, -1):
        if prices[j] > prices[i]:
            break
        span_value += 1

    span[i] = span_value

return span

stock_prices = [100, 80, 60, 70, 60, 75, 85]
span = calculate_span(stock_prices)

print("Stock Prices: " + str(stock_prices))
print("Spans: " + str(span))

// C# code to solve stock span problem - brute force
using System;

class StockSpan {
    public static void Main() {
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        int[] span = CalculateSpan(prices);

        Console.WriteLine("Stock Prices: " + string.Join(" ", prices));
        Console.WriteLine("Spans: " + string.Join(" ", span));
    }

    public static int[] CalculateSpan(int[] prices) {
        int n = prices.Length;
        int[] span = new int[n];
        Array.Fill(span, 1);

        for (int i = 0; i < n; ++i) {
            int spanValue = 1;

            for (int j = i - 1; j >= 0 && prices[j] <= prices[i]; --j) {
                spanValue++;
            }

            span[i] = spanValue;
        }

        return span;
    }
}

Output:

Stock Prices: 100 80 60 70 60 75 85 
Spans: 1 1 1 2 1 4 6

Time Complexity: O(n^2).

Space Complexity: O(1).