top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

What is Stock Span problem?

+2 votes
2,519 views
What is Stock Span problem?
posted May 13, 2014 by Atul Mishra

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
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 span of stock’s price for all n days.

The span Si of the stock’s price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.

For example, if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}

Source: http://www.geeksforgeeks.org/the-stock-span-problem/

1 Answer

0 votes

Source: http://www.geeksforgeeks.org/the-stock-span-problem/

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 span of stock’s price for all n days.

The span Si of the stock’s price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.

For example, if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}
enter image description here

Algo1: A Simple but inefficient method
Traverse the input price array. For every element being visited, traverse elements on left of it and increment the span value of it while elements on the left side are smaller.

Algo2: A Linear Time Complexity Method
We see that S[i] on day i can be easily computed if we know the closest day preceding i, such that the price is greater than on that day than the price on day i. If such a day exists, let’s call it h(i), otherwise, we define h(i) = -1.

The span is now computed as S[i] = i – h(i). See the following diagram.

enter image description here

To implement this logic, we use a stack as an abstract data type to store the days i, h(i), h(h(i)) and so on. When we go from day i-1 to i, we pop the days when the price of the stock was less than or equal to price[i] and then push the value of day i back into the stack.

answer May 13, 2014 by Santosh Prasad
Similar Questions
+2 votes

Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that they sum up to S.

+5 votes

Josephus Problem talks about a problem where there are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

0 votes

Problem: You have given a stock prices for next 10 days. Find out: max benefit in best time complexity in buy and sell 1 share ?
Condition: Share must be sold any day after buying date.

For ex:
Share price in thousands
5 1 4 6 7 8 4 3 7 9
Max benefit 9 – 1 = 8 thousand

+4 votes

If we delete the mth number from a circle which is composed of numbers 0, 1, …, n-1 counting from 0 at every time, what is the last number?

For example, a circle is composed of five numbers 0, 1, 2, 3, 4. If we delete the 3rd number at every time, the deleted numbers are in order of 2, 0, 4, 1, so the last remaining number is 3.

...