Afzal has been working with an organization called 'Money Traders for the past few years. The organization is in the money trading business. His manager assigned him a task.
Given an array ’prices’ which denotes stock prices for ’n’ days, e.g., 'prices[ i ]' = price of the stock at ‘ith’ day, 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 backward) for which the price of the stock was less than today's price.
Input: ‘n’ = 7, ‘prices’ = [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]
Explanation:
On the sixth day, when the stock price was 75,
The span came out to be 4 because the last three prices(plus today) were less than the current or the sixth day's price.
Similarly, we can deduce the remaining results.
You don’t need to print anything. Just implement the given function
The first line of each test case contains an integer ‘n’ denoting the number of days.
The second line of each test case contains ‘n’ integers denoting the prices of the stocks.
Return an array that contains the stock’s span for each day.
4
2 1 2 4
1 1 2 4
Number of consecutive days with price smaller than 0th day(starting from 0th day) = 1
Number of consecutive days with price smaller than 1st day(starting from 1st day) = 1
Number of consecutive days with price smaller than 2nd day(starting from 2nd day) = 2
Number of consecutive days with price smaller than 3rd day(starting from 3rd day) = 4
6
20 12 1 28 16 20
1 1 1 4 1 2
Number of consecutive days with price smaller than 0th day(starting from 0th day) = 1
Number of consecutive days with price smaller than 1st day(starting from 1st day) = 1
Number of consecutive days with price smaller than 2nd day(starting from 2nd day) = 1
Number of consecutive days with price smaller than 3rd day(starting from 3rd day) = 4
Number of consecutive days with price smaller than 3rd day(starting from 4th day) = 1
Number of consecutive days with price smaller than 3rd day(starting from 5th day) = 2
The expected time complexity is O(n).
1 <= n <= 10^6
1 <= prices[i] <= 10^9
Time Limit: 1 sec
Can you think about a straightforward solution using two loops?
In the naive approach, We can iterate over the prices array. For the ‘ith’ day, we can start iterating over the previous prices starting from (i-1)th day, and then for each last day, if the price is less than the price of the ith day, then we increase the span of the ith day by 1 otherwise we stop iterating over the previous prices.
The steps are as follows:-
Function findStockSpans(vector<int>& prices):
O(n * n ), Where ‘n’ denotes the number of days.
We are Iterating over the ‘prices’ array, and for each day, we are iterating over the previous days. Iterating over the previous days has the worst time complexity of O( n ), and iterating over the ‘prices’ array has an O ( n ) time complexity.
Hence the time complexity is O( n * n ).
O( 1 ).
We are not using any extra memory. The array required for ‘ANS’ does not count in Auxiliary Space.
Hence space complexity is O( 1 ).
All tags
Sort by
Interview problems
Python easy solution
def findStockSpans(arr: List[int]) -> List[int]:
st=[]
ans=[0]*len(arr)
ans[0]=1
for i,num in enumerate(arr):
while st and num>arr[st[-1]]:
st.pop()
if st:
ans[i]=i-st[-1]
else:
ans[i]=i+1
st.append(i)
return ansInterview problems
Easy C++ Solution using Stack
HINT : JUST Solve previous greater (or equal) element and modify it :)
vector<int> findStockSpans(vector<int>& prices) {
stack<pair<int,int>> st;
vector<int> v;
int n = prices.size();
for(int i=0;i<n;i++){
while(!st.empty() && st.top().first<prices[i]){
st.pop();
}
if(!st.empty() && st.top().first>=prices[i]){
v.push_back(i-(st.top().second));
st.push({prices[i], i});
}
if(st.empty()){
v.push_back(i-(-1));
st.push({prices[i], i});
}
}
return v;
}Interview problems
JAVA easiest solution with stack
import java.util.Stack;
public class Solution {
public static int[] findStockSpans(int []prices) {
int n = prices.length;
int[] output = new int[n];
Stack<int[]> st = new Stack<>(); // Stack to store pairs of (price, index)
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && st.peek()[0] < prices[i]) {
st.pop();
}
if (st.isEmpty()) {
output[i] = i+1; // If the stack is empty, span is i + 1
} else {
output[i] = i - st.peek()[1]; // Calculate the span as the difference between the current index and the index of the top of the stack
}
st.push(new int[]{prices[i], i}); // Push the current price and its index onto the stack
}
return output;
}}
Interview problems
JAVA-Solution (Optimized)-Stockspan
import java.util.*;
public class Solution {
// Define a pair class to store value and index
public static class pair{
int val;
int ind;
pair(int val, int ind){
this.val = val;
this.ind = ind;
}
}
public static int[] NGE_Left(int arr[], int n){
int res[] = new int[n];
Stack<pair> s = new Stack<>();
for(int i = 0; i < n; i++){
while(s.size() > 0 && s.peek().val < arr[i]){
s.pop();
}
if(s.size() == 0){
res[i] = -1;
} else if(s.peek().val >= arr[i]){
res[i] = s.peek().ind;
}
s.push(new pair(arr[i], i));
}
return res;
}
public static int[] findStockSpans(int []prices) {
int ans[] = NGE_Left(prices, prices.length);
for(int i = 0; i < prices.length; i++){
ans[i] = i - ans[i];
}
return ans;
}
}
Interview problems
C++||Stack||Explanation||Dry Run
Example:
arr=[100,80,60,70,60,75,85]
ans=[0,0,0,0,0,0,0,0]
i=0
stack=[0] ans[0]=1
i=1
stack=[0,1] ans[1]=1
i=2
stack=[0,1,2] ans[2]=1
i=3
stack=[0,1,3] ans[3]=1+ans[2]=1+1=2
i=4
stack=[0,1,3,4] ans[4]=1
i=5
stack=[0,1,5] ans[5]=ans[3]+ans[4]+1=2+1+1=4
i=6
stack=[0] ans[6]=1++ans[1]+ans[5]=1+4+1=6
vector<int> findStockSpans(vector<int>& prices) {
int n=prices.size();
stack<int> st;
vector<int> ans(n,0);
for(int i=0;i<n;i++){
while(st.empty()==false && prices[st.top()]<prices[i]){
//count for self element
ans[i]+=ans[st.top()];
st.pop();
}
ans[i]++;
st.push(i);
}
return ans;
}
Interview problems
EASY C++
vector<int> findStockSpans(vector<int> &prices) {
stack<pair<int,int>> st;
vector<int> ans;
for (int &a : prices) {
int span = 1;
while ( !st.empty() && st.top().first < a) {
span+=st.top().second;
st.pop();
}
ans.push_back(span);
st.push({a,span});
}
return ans;
}
Interview problems
Stock Span | O(n) C++ easy solution
vector<int> findStockSpans(vector<int>& price) {
int n= price.size();
stack<int> s;
vector<int>v(n,1);
for(int i=n-1 ;i>=0;i--){
if(s.empty()) s.push(i);
else
{
while(!s.empty() && price[i]>=price[s.top()])
{
v[s.top()] = s.top()-i;
s.pop();
}
s.push(i);
}
}
//v[0]=1;
while(!s.empty())
{
v[s.top()] =v[s.top()]+s.top();
s.pop();
}
return v;
}
Interview problems
Simple code just work on the pushing of indices
import java.util.*;
public class Solution {
public static int[] findStockSpans(int []prices) {
// Write your code here.
Stack<Integer> s=new Stack<>();
int n=prices.length;
int[] ans=new int[n];
for(int i=0;i<n;i++){
while(!s.isEmpty()&&prices[i]>prices[s.peek()]){
s.pop();
}
if(s.isEmpty()){
ans[i]=i+1;
}
else if(!s.isEmpty()){
ans[i]=i-s.peek();
}
s.push(i);
}
return ans;
}
}
Interview problems
C++ || Easy solution
#include<bits/stdc++.h>
vector<int> prevGreater(vector<int> &prices){
stack<int> s;
int n = prices.size();
vector<int> ans(n, 1);
for(int i=0; i<n; i++){
int curr = prices[i];
while(!s.empty() && prices[s.top()] < curr){
s.pop();
}
if(!s.empty()) ans[i] = s.top();
else ans[i] = -1;
s.push(i);
}
return ans;
}
vector<int> findStockSpans(vector<int>& prices) {
vector<int> prevG = prevGreater(prices);
int n = prices.size();
vector<int> ans(n, 1);
for(int i=1; i<n; i++){
ans[i] = i - prevG[i];
}
return ans;
}
Interview problems
c++ easy implementation using stack o(n) complexity
#include<bits/stdc++.h>
vector<int> findStockSpans(vector<int>& prices) {
int n=prices.size();
stack<pair<int,int>> st;
vector<int> ans(n,0);
for(int i=0; i<n; i++){
int span=1;
while(!st.empty() && prices[i]> st.top().first){
span +=st.top().second;
st.pop();
}
st.push({prices[i],span});
ans[i]=span;
}
return ans;
}
