Introduction

The Stock Span Problem is a popular question often asked in technical interviews. The task is to compute how many consecutive days (including the current day) the stock price has been less than or equal to the current day's price. This "span" helps in analyzing stock market trends over time.

In this blog post, we will solve the Stock Span problem efficiently using stacks in Java. We'll also ensure that our solution runs in O(n) time complexity, where n is the number of days.

Problem Statement

Given a list of daily stock prices, we need to calculate the stock span for each day. The stock span for a given day is defined as the maximum number of consecutive days, including the current day, for which the price of the stock on that day was less than or equal to the stock price on the current day.

Example:

Input: stockPrices = [55, 34, 22, 23, 27, 88, 70, 42, 51, 100]
Output: spanResult = [1, 1, 1, 2, 3, 6, 1, 1, 3, 10]

Explanation:

On day 1 (price: 55), no previous days, so the span is 1.
On day 2 (price: 34), the price on day 1 is greater than 34, so the span is 1.
On day 3 (price: 22), the price on day 2 is greater than 22, so the span is 1.
On day 4 (price: 23), price on day 3 is less than 23, so span is 2.
On day 5 (price: 27), price on day 4 and day 3 are less than 27, so span is 3.
On day 6 (price: 88), all previous prices are less than 88, so span is 6.
On day 7 (price: 70), only day 6 price is greater than 70, so span is 1.
And so on...

Approach

Key Concepts:

Using a Stack: A stack can help you keep track of the daily indices. For each day, we pop from the stack until we find a day on which the stock price is greater than the current day's price.
Efficient Calculation: Instead of using nested loops, we can compute the span in O(n) time by maintaining a stack that stores indices of days with prices greater than the current day’s price.

Java Code Implementation

Main Class

import java.util.Arrays; 

public class Main {

    public static void main(String[] args) {
        int stockPrices[] = {55, 34, 22, 23, 27, 88, 70, 42, 51, 100};
        int[] spanResult = StockSpan.stockSpan(stockPrices);

        System.out.println("Stock prices: " + Arrays.toString(stockPrices));
        System.out.println("Span results: " + Arrays.toString(spanResult));
    }
}

StockSpan Class

import java.util.Stack;

public class StockSpan {

    // Prevent instantiation of the class
    private StockSpan() {
        throw new AssertionError("Cannot be instantiated");
    }

    // Method to calculate the stock span for each day
    public static int[] stockSpan(int[] stockPrices) {
        // Handle null input
        if (stockPrices == null) {
            throw new IllegalArgumentException("Prices array cannot be null");
        }

        Stack<Integer> dayStack = new Stack<>();
        int[] spanResult = new int[stockPrices.length];

        // Initialize span for the first day
        spanResult[0] = 1;  // First day always has span 1
        dayStack.push(0);  // Push the first day index onto the stack

        // Traverse the stock prices starting from the second day
        for (int i = 1; i < stockPrices.length; i++) {
            // Pop all the indices from the stack where the stock price is less than or equal to current day's price
            while (!dayStack.isEmpty() && stockPrices[i] > stockPrices[dayStack.peek()]) {
                dayStack.pop();
            }

            // Calculate the span for the current day
            if (dayStack.isEmpty()) {
                spanResult[i] = i + 1;  // No greater price found, span is the total number of days
            } else {
                spanResult[i] = i - dayStack.peek();  // Span is the difference between current day and last day with greater price
            }

            // Push current day's index onto the stack
            dayStack.push(i);
        }

        return spanResult;  // Return the span results for all days
    }
}

Explanation

Step 1: Initial Setup

We first initialize the stack and span result array. The span of the first day is always 1, so we set spanResult[0] = 1 and push the index 0 onto the stack.

spanResult[0] = 1;
dayStack.push(0);

Step 2: Iterate Over the Prices

For each day from day 1 to day n-1, we:
1. Pop from the stack while the current price is greater than the price at the top of the stack.
2. If the stack is empty, it means no previous day has a greater price, so the span is i + 1.
3. Otherwise, calculate the span as i - dayStack.peek() (the difference between the current day and the last day with a greater price).

for (int i = 1; i < stockPrices.length; i++) {
    while (!dayStack.isEmpty() && stockPrices[i] > stockPrices[dayStack.peek()]) {
        dayStack.pop();
    }

    spanResult[i] = dayStack.isEmpty() ? i + 1 : i - dayStack.peek();
    dayStack.push(i);
}

Step 3: Return the Result

After calculating the spans for each day, we return the spanResult array.

return spanResult;

Example Output:

Stock prices: [55, 34, 22, 23, 27, 88, 70, 42, 51, 100]
Span results: [1, 1, 1, 2, 3, 6, 1, 1, 3, 10]

Explanation of Output:

The stock prices [55, 34, 22, 23, 27, 88, 70, 42, 51, 100] result in spans [1, 1, 1, 2, 3, 6, 1, 1, 3, 10].
On day 6, the price is 88, and all previous days' prices are less than or equal to 88, resulting in a span of 6.
On day 10, the price is 100, which is greater than all previous prices, giving a span of 10.

Time Complexity

Time Complexity: O(n), where n is the number of days. Each price is pushed and popped from the stack at most once, so the time complexity is linear.
Space Complexity: O(n) because of the stack that stores the indices.

Conclusion

In this blog post, we solved the Stock Span Problem using stacks. The stack efficiently calculates the number of consecutive days where the price is less than or equal to the current day's price, making the algorithm run in O(n) time complexity. This approach is optimal compared to a brute force approach that would take O(n²) time.

Java Guides

Search This Blog

Java Coding Challenge - Stock Span Problem