Coding Recipies: Stock Span Problem

Problem Statment :
We are given list price of a stock for N days, find the stock span of each day. Stock spam is defined as the consecutive number of days where the stock price was less or equal to the given day stock price.

For ex. for P = {11, 9, 7, 5, 4, 6, 8, 10, 7, 9} the span is S = {1, 1, 1, 1, 1, 3, 4, 7, 1, 2}

Solution :

I hope the solution looks evident by looking at the graph, so we plot the span values of each stock price below to make it much more meaningful and clear.

We will be discussing multiple approaches to solve the problem.

Approach 1 :

We will first consider the naive solution which will have a time complexity of O(n^2).

Here for each item traverse on the left of the array until you find the element bigger than the current one. For every move towards the left increment the counter of the current element by 1.

  int[] solve1(int[] stocks) {
 int len = stocks.length, i , j ;
 int[] span = new int[len];
 span[0] = 1;
  
 for (i = 1; i < len; i++) { 
  for (j = i - 1, span[i] = 1; j >= 0 && stocks[i] >= stocks[j]; j--, span[i]++);
 }
 return span;
  }

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

We surely can do better than this, moving to the next approach

Approach 2 :

In this approach, we will consider a stack-based solution to improve Time complexity.
Here the idea is if the next element is smaller then the stock span of that element is 1 (eg, 70, 65) otherwise if the next element is greater than the top element (eg, 70, 65, 80) then there is possibility that incoming element is greater than further elements in the stack so keep popping until you find a greater element index than the current element and calculate the span using span[i] = i - price[stack.peek()] or otherwise if the stack is empty span[i] = i+1.

Let us write the code for this. (i am writing a code in order to understand the logic, you improvise it to make it shortened).

  int[] solve(int[] stocks)
    {
 Stack<Integer> stack = new Stack<Integer>();
 stack.push(0);
 int[] sol = new int[stocks.length];
 sol[0]=1;
  
 for(int i=1;i<stocks.length;i++)
 {
     //if incoming element is small, Pop until u find greater element index in the stack 
     for(;!stack.isEmpty() && stocks[stack.peek()] < stocks[i]; stack.pop());
  
     sol[i] = stack.isEmpty() ? i + 1: i - stack.peek();
     stack.push(i);
 }
 System.out.println(Arrays.toString(sol));
 return sol;
    }

In spite of the fact that there are nested loops in the above code, the time complexity is O(n) because we are traversing all the elements just once. In the worst case, we may have to put all the elements into the stack and then pop out all the elements (eg. 80,70, 60, 50, 40, 90) so the complexity would be O(2*n) which is of the order of O(n).

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

Executable Code below:

Please post your comments and suggestions.
Happy Coding !! :)

Coding Recipies

20 Jun 2019

Stock Span Problem

1 comment: