New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Stock Span

Contributed by

Amit Shaw

Last Updated: 23 Feb, 2023

Medium

0/80

Avg time to solve 20 mins

Success Rate 65 %

6 upvotes

Problem Statement

Afzal 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. 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.

Example:

Input: ‘N’ = 7,  ‘PRICES’ = [100, 80, 60, 70, 60, 75, 85]

Output: [1, 1, 1, 2, 1, 4, 6]

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.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line will contain the integer 'T,' denoting the number of test cases.

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.

Output format :

For each test case, return an array that contains the stock’s span for each day.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
1 <= A[i] <= 10^9
Sum of ‘N’ <= 10^5
Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

1 1 2 4
1 2

Explanation Of Sample Input 1 :

For the first case:
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 

For the second case:
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) = 2

Sample Input 2 :

2
6
20 12 1 28 16 20 
5
2 14 29 21 11

Sample Output 2 :

1 1 1 4 1 2 
1 2 3 1 1

Auto

Console