Stock Span Problem

Problem Statement

Given a list of prices of a stock for N days. The task is to find the stack span for each day.
Stock span can be defined as the number of consecutive days before the current day where the price of the stack was equal to or less than the current price.

Examples:

Input: A[] = [100,60,70,65,80,85]
Output: [1,1,2,1,4,5]
Explanation: Explained in image above.

Input: [31, 27, 14, 21, 30, 22]
Output: [1, 1, 1, 2, 4, 1]

Brute Force Approach

A simple approach to solve this problem is to run two nested loops and for each element, find the maximum length such that all consecutive elements are smaller than the current element.
In case a large element is found, terminate the loop.

C++ Code

void calculateSpan(int price[], int n, int S[]) {
  S[0] = 1;
  for (int i = 1; i < n; i++) {
    S[i] = 1;
    for (int j = i - 1;
      (j >= 0) &&
      (price[i] >= price[j]); j--)
      S[i]++;
  }
}

Java Code

static void calculateSpan(int price[], int n, int S[]) {
  S[0] = 1;
  for (int i = 1; i < n; i++) {
    S[i] = 1;
    for (int j = i - 1;
      (j >= 0) && (price[i] >= price[j]); j--)
      S[i]++;
  }
}

Python Code

def calculateSpan(price, n, S):
    S[0] = 1
    for i in range(1, n, 1):
        S[i] = 1
        j = i - 1
        while (j>= 0) and (price[i] >= price[j]) :
                       S[i] += 1
                       j -= 1

Time Complexity:O(N^2), where N is total size of the array
Space Complexity:O(1), as no extra space is used

Approach 2: Stack

Instead of traversing through all previous elements of the current element, we can use the Stack data structure which can solve the problem in linear time.
The approach of this problem is very similar to Next Greater Element. But, the indices of the next greater element is stored instead of the element itself.

Algorithm

• Initialise an array S[0] = 1 for day 0.
• Initialise a stack and push the index of the first day into the stack.
• Traverse a loop from 1 to N and for each iteration, do the following:
  • If the stack is not empty and price of current element is greater than the top of stack, pop the element.
  • Else if, stack is not empty then, subtract index from S[i], i.e. S[i] = i – S.top().
  • Else, S[i] =  i + 1
• Push the current index i into the stack.

C++ Implementation

void calculateSpan(int price[], int n, int S[]) {
  stack < int > st;
  st.push(0);
  S[0] = 1;
  for (int i = 1; i < n; i++) {
    while (!st.empty() && price[st.top()] < price[i])
      st.pop();
 
    S[i] = (st.empty()) ? (i + 1) : (i - st.top());
    st.push(i);
  }
}

Java Implementation

static void calculateSpan(int price[], int n, int S[]) {
  Stack < Integer > st = new Stack < > ();
  st.push(0);
 
  S[0] = 1;
  for (int i = 1; i < n; i++) {
    while (!st.empty() && price[st.peek()] <= price[i])
      st.pop();
 
    S[i] = (st.empty()) ? (i + 1) : (i - st.peek());
    st.push(i);
  }
}

Python Implementation

def calculateSpan(price, S):
     
    n = len(price)
    st = []
    st.append(0)
 
    S[0] = 1
 
    for i in range(1, n):
        while( len(st) > 0 and price[st[-1]] <= price[i]):
            st.pop()
 
        S[i] = i + 1 if len(st) <= 0 else (i - st[-1])
 
        st.append(i)

Time Complexity:O(N), where N is total size of the array
Space Complexity:O(1), as no extra space is used.

Practice Questions

Best time to buy and sell stocks

FAQs

What is Stock Span Problem?
Stock span can be defined as the number of consecutive days before the current day where the price of the stack was equal to or less than the current price.

What is the most efficient approach to solving the stock span problem?
The stack-based approach is the most efficient approach to solve the problem. The time complexity is O(N) and space complexity is O(1).