Stock Span Problem

Calculate the span of stock prices for each day

Language Selection

Choose your preferred programming language

Showing: Python

Stock Span Problem

Problem Statement

The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate the span of stock’s price for all n days. The span of the stock’s price on a given day is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to today’s price.

Input/Output Specifications

  • Input: An array of stock prices prices where 1 <= prices.length <= 10^5 and 0 <= prices[i] <= 10^5
  • Output: An array where each element represents the span for that day

Constraints

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^5

Examples

Example 1:

Input: prices = [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]
Explanation:
Day 0: Price 100, span = 1 (only current day)
Day 1: Price 80, span = 1 (80 < 100)
Day 2: Price 60, span = 1 (60 < 80)
Day 3: Price 70, span = 2 (70 > 60, so includes day 2)
Day 4: Price 60, span = 1 (60 < 70)
Day 5: Price 75, span = 4 (75 > 60, 70, 80, so includes days 4,3,2,1)
Day 6: Price 85, span = 6 (85 > 75, 60, 70, 80, 100, so includes days 5,4,3,2,1,0)

Example 2:

Input: prices = [10, 4, 5, 90, 120, 80]
Output: [1, 1, 2, 4, 5, 1]

Example 3:

Input: prices = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]

Solution Approaches

Approach 1: Monotonic Stack - Optimal

Algorithm Explanation:

  1. Use a stack to store indices of prices in decreasing order
  2. For each price, pop all smaller prices from the stack
  3. Calculate span as the difference between current index and the index of the next greater element
  4. Push current index to the stack

Implementation:

Python:

def calculateSpan(prices):
    """
    Calculate stock span using monotonic stack
    Time: O(n)
    Space: O(n)
    """
    if not prices:
        return []
    
    n = len(prices)
    span = [0] * n
    stack = []  # Stack to store indices
    
    for i in range(n):
        # Pop all indices with prices smaller than current price
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()
        
        # Calculate span
        if stack:
            span[i] = i - stack[-1]
        else:
            span[i] = i + 1  # All previous days
        
        # Push current index
        stack.append(i)
    
    return span

Java:

import java.util.*;

class Solution {
    /**
     * Calculate stock span using monotonic stack
     * Time: O(n)
     * Space: O(n)
     */
    public int[] calculateSpan(int[] prices) {
        if (prices == null || prices.length == 0) {
            return new int[0];
        }
        
        int n = prices.length;
        int[] span = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            // Pop all indices with prices smaller than current price
            while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
                stack.pop();
            }
            
            // Calculate span
            if (stack.isEmpty()) {
                span[i] = i + 1;  // All previous days
            } else {
                span[i] = i - stack.peek();
            }
            
            // Push current index
            stack.push(i);
        }
        
        return span;
    }
}

Go:

func calculateSpan(prices []int) []int {
    /**
     * Calculate stock span using monotonic stack
     * Time: O(n)
     * Space: O(n)
     */
    if len(prices) == 0 {
        return []int{}
    }
    
    n := len(prices)
    span := make([]int, n)
    var stack []int  // Stack to store indices
    
    for i := 0; i < n; i++ {
        // Pop all indices with prices smaller than current price
        for len(stack) > 0 && prices[stack[len(stack)-1]] <= prices[i] {
            stack = stack[:len(stack)-1]
        }
        
        // Calculate span
        if len(stack) == 0 {
            span[i] = i + 1  // All previous days
        } else {
            span[i] = i - stack[len(stack)-1]
        }
        
        // Push current index
        stack = append(stack, i)
    }
    
    return span
}

JavaScript:

/**
 * Calculate stock span using monotonic stack
 * Time: O(n)
 * Space: O(n)
 */
function calculateSpan(prices) {
    if (!prices || prices.length === 0) {
        return [];
    }
    
    const n = prices.length;
    const span = new Array(n);
    const stack = [];  // Stack to store indices
    
    for (let i = 0; i < n; i++) {
        // Pop all indices with prices smaller than current price
        while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
            stack.pop();
        }
        
        // Calculate span
        if (stack.length === 0) {
            span[i] = i + 1;  // All previous days
        } else {
            span[i] = i - stack[stack.length - 1];
        }
        
        // Push current index
        stack.push(i);
    }
    
    return span;
}

C#:

using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Calculate stock span using monotonic stack
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public int[] CalculateSpan(int[] prices) {
        if (prices == null || prices.Length == 0) {
            return new int[0];
        }
        
        int n = prices.Length;
        int[] span = new int[n];
        var stack = new Stack<int>();
        
        for (int i = 0; i < n; i++) {
            // Pop all indices with prices smaller than current price
            while (stack.Count > 0 && prices[stack.Peek()] <= prices[i]) {
                stack.Pop();
            }
            
            // Calculate span
            if (stack.Count == 0) {
                span[i] = i + 1;  // All previous days
            } else {
                span[i] = i - stack.Peek();
            }
            
            // Push current index
            stack.Push(i);
        }
        
        return span;
    }
}

Complexity Analysis:

  • Time Complexity: O(n) - Each element is pushed and popped at most once
  • Space Complexity: O(n) - Stack can store at most n elements

Approach 2: Brute Force

Algorithm Explanation:

  1. For each day, count consecutive days backward where price is less than or equal to current price
  2. Use nested loops to check each previous day

Implementation:

Python:

def calculateSpan_brute(prices):
    """
    Calculate stock span using brute force
    Time: O(n^2)
    Space: O(1)
    """
    if not prices:
        return []
    
    n = len(prices)
    span = [0] * n
    
    for i in range(n):
        span[i] = 1  # At least current day
        
        # Count consecutive days backward
        j = i - 1
        while j >= 0 and prices[j] <= prices[i]:
            span[i] += 1
            j -= 1
    
    return span

Complexity Analysis:

  • Time Complexity: O(n^2) - For each day, potentially check all previous days
  • Space Complexity: O(1) - Only storing the result

Key Insights

  1. Monotonic Stack: Maintains elements in decreasing order
  2. Next Greater Element: Similar to finding next greater element problem
  3. Span Calculation: Difference between current index and next greater element index
  4. Stack Operations: Pop smaller elements, push current element

Edge Cases

  1. Empty Array: Return empty array
  2. Single Element: Return [1]
  3. Increasing Prices: All spans are consecutive
  4. Decreasing Prices: All spans are 1
  5. Equal Prices: Include days with equal prices

Test Cases

def test_calculateSpan():
    # Test case 1
    prices1 = [100, 80, 60, 70, 60, 75, 85]
    assert calculateSpan(prices1) == [1, 1, 1, 2, 1, 4, 6]
    
    # Test case 2
    prices2 = [10, 4, 5, 90, 120, 80]
    assert calculateSpan(prices2) == [1, 1, 2, 4, 5, 1]
    
    # Test case 3
    prices3 = [1, 2, 3, 4, 5]
    assert calculateSpan(prices3) == [1, 2, 3, 4, 5]
    
    # Test case 4
    prices4 = [5, 4, 3, 2, 1]
    assert calculateSpan(prices4) == [1, 1, 1, 1, 1]
    
    # Test case 5
    prices5 = [1]
    assert calculateSpan(prices5) == [1]
    
    print("All tests passed!")

test_calculateSpan()

Follow-up Questions

  1. Next Greater Element: Find next greater element for each element?
  2. Previous Greater Element: Find previous greater element for each element?
  3. Largest Rectangle: Find largest rectangle in histogram?
  4. Trapping Rainwater: Calculate trapped rainwater?
  5. Daily Temperatures: Find next warmer day?

Common Mistakes

  1. Wrong Stack Order: Not maintaining decreasing order in stack
  2. Incorrect Span Calculation: Wrong formula for calculating span
  3. Index Confusion: Mixing up indices and values
  4. Edge Case Handling: Not handling empty array or single element
  5. Stack Operations: Incorrect push/pop operations

Interview Tips

  1. Start with Brute Force: Show understanding of the problem
  2. Optimize with Stack: Explain the monotonic stack approach
  3. Discuss Trade-offs: Compare time and space complexities
  4. Handle Edge Cases: Mention empty array and single element cases
  5. Code Carefully: Pay attention to stack operations and span calculation

Concept Explanations

Monotonic Stack: A stack that maintains elements in a specific order (increasing or decreasing). For this problem, we maintain decreasing order to efficiently find the next greater element.

Stock Span: The number of consecutive days (including current day) where the stock price was less than or equal to the current day’s price.

Next Greater Element: The first element to the right that is greater than the current element. This is a fundamental problem that appears in many variations.

When to Use: Use this pattern when you need to find the next greater/lesser element or calculate spans/ranges based on element relationships.