Amit has been working with an organization called 'Money Traders' for the past few years. The organization is into the money trading business. His manager assigned him a task. For a given array/list of stock's prices for N days, find the stock's span for each day.
The span of the stock's price today is defined as the maximum number of consecutive days(starting from today and going backwards) for which the price of the stock was less than today's price.
Explanation:
For the stock prices [100, 80, 60, 70, 60, 75, 85], the span of each day is calculated by counting consecutive previous days with a price less than or equal to today's price:
Day 1 (100): No previous days, span = 1.
Day 2 (80): Less than 100, span = 1.
Day 3 (60): Less than 80, span = 1.
Day 4 (70): Greater than 60, span = 2.
Day 5 (60): Less than 70, span = 1.
Day 6 (75): Greater than 60, 70, and 60, span = 4.
Day 7 (85): Greater than all previous days, span = 6.
Final spans: [1, 1, 1, 2, 1, 4, 6].
Amit has to return an array/list of spans corresponding to each day's stock's price. Help him to achieve the task.
The first line of input contains an integer N, denoting the total number of days.
The second line of input contains the stock prices of each day. A single space will separate them.
The only line of output will print the span for each day's stock price. A single space will separate them.
You are not required to print the expected output explicitly. It has already been taken care of. Just store the values of output in the spans array.
0 <= N <= 10^7
1 <= X <= 10^9
Where X denotes the stock's price for a day.
Time Limit: 1 second
4
10 10 10 10
1 1 1 1
8
60 70 80 100 90 75 80 120
1 2 3 4 1 1 2 8
All tags
Sort by
CPP solution
#include<stack>
void calculateSpan(int prices[], int n, int spans[]) {
//Write your code here
stack<int> s;
for(int i=0;i<n;i++){
while(!s.empty()){
if(prices[i]>prices[s.top()]){
s.pop();
}
else{
break;
}
}
if(s.empty()){
spans[i]=i+1;
}
else{
spans[i]=i-s.top();
}
s.push(i);
}
}Interview problems
Previous greater element approach
#include<stack> int* stockSpan(int *price, int size) { int* arr; arr=new int[size]; stack<int>s; for(int i=0;i<size;i++) { while(!s.empty() and price[s.top()]<price[i]){s.pop();} if(s.empty()) arr[i] = -1; else arr[i]=(s.top()); s.push(i); } for(int i=0;i<size;i++){ arr[i]=i-arr[i]; } return arr;
}
Interview problems
Discussion thread on Interview Problem | Stock Span
Hey everyone, creating this thread to discuss the interview problem - Stock Span.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Stock Span
