Stack: Stock Span Problem

Problem Statement:

You are given an array, that represents the stock of the ith day.

You need to return the stock span for the ith day, i.e the count of consecutive days the stock price increases or equal to that day.

Example:

Input: arr[] = [10, 8, 4, 12]

Output: [1, 1, 1, 4]

Solution 1: Bruteforce approach

For each day, we will check how many consecutive previous days stock is less than or equal to.

For that, we use 2 nested loops, then move leftwards from the current index and until the current element is greater than the element in check.

Time Complexity: O(n*n)
Space Complexity: O(1)

Solution 2: Efficient approach

In the previous approach, we will start traverse to the left till we get the greater element.

So now, this problem is reduced to find the previous greater element.

We can use stack to solve the problem in linear time.

Take a result array “res” and initialize res[0] = 1.

Take a stack and push the index of the first element into the stack.

Then from 1 to N, check:

> if the stack is not empty and the price of current element is greater than the top of the stack, pop the element.

> else, if stack is not empty, then update the result array res[i] = i – Stack.top()

> else, res[i] = i + 1

Push current element index into the stack.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> solution_1(vector<int>& arr) 
{

    int n = arr.size(); 
    vector<int> span(n, 1);
    
    for (int i = 1; i < n; i++) 
    {
        
        for (int j = i - 1; (j >= 0)
                      && (arr[i] >= arr[j]); j--) 
        {
            span[i]++;
        }
    }

    return span;
}

vector<int> solution_2(vector<int>& arr) 
{

    int n = arr.size(); 
    vector<int> span(n, 1);
	stack <int> st;
	
	st.push(0);
  	span[0] = 1;

  	for (int i = 1; i < n; i++) 
    {
    	while (!st.empty() && arr[st.top()] < arr[i])
      	st.pop();
 
    	span[i] = (st.empty()) ? (i + 1) : (i - st.top());
   		st.push(i);
  }
    return span;  
}


int main() 
{
  
    vector<int> arr = {10, 8, 4, 12};

    vector<int> span = solution_1(arr);
    for (int x : span)
     {
        cout << x << " ";
    }
    cout<<"\n";

    span = solution_2(arr);
    for (int x : span) 
    {
        cout << x << " ";
    }

    return 0;
}

Output

1 1 1 4 
1 1 1 4