An array prices contains the stock price for every day in chronological order. For each day, find the maximum number of consecutive days ending on the current day with prices less than or equal to the current price.
Return an array containing the span for every day. The current day always belongs to the span, so every span is at least 1.
Example 1
Input: prices = [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]
Explanation: Price 75 covers prices [60, 70, 60, 75], giving span 4. Price 85 covers [80, 60, 70, 60, 75, 85], giving span 6; price 100 stops further extension.
Example 2
Input: prices = [50, 50, 50]
Output: [1, 2, 3]
Explanation: Equal prices remain valid because every earlier price only needs to be less than or equal to the current price.
Brute Force Approach
A stock span counts the current day and all consecutive previous days with prices less than or equal to the current price. The first greater price on the left stops the span.
A backward scan directly follows this definition and is easy to understand. However, the same prices may be checked repeatedly, making the approach slow for an increasing price sequence.
Algorithm
Create an answer array of size
Nand initialize every position with1, because every span includes the current day.Traverse all days from left to right to calculate the span for each price.
Set
previousDay = currentDay - 1to begin checking prices immediately before the current day.Move backward while the previous price is less than or equal to the current price, because such days belong to the consecutive span.
Increase the current span for every valid previous day.
Stop the backward scan when a greater price is found, because the span cannot cross that day.
Store the calculated span in the corresponding answer position.
Return the completed answer array after processing all days.
Dry Run
Stock Span Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Calculates every stock span with backward scans. vector<int> calculateSpan(vector<int>& prices) { int n = prices.size(); vector<int> spans(n, 1); // Each day receives one independent backward scan. for (int currentDay = 0; currentDay < n; currentDay++) { int previousDay = currentDay - 1; // Valid consecutive prices extend the current span. while (previousDay >= 0 && prices[previousDay] <= prices[currentDay]) { spans[currentDay]++; previousDay--; } } return spans; }};// Driver codeint main() { vector<int> prices = {100, 80, 60, 70, 60, 75, 85}; Solution obj; vector<int> spans = obj.calculateSpan(prices); for (int span : spans) cout << span << " "; return 0;}Note: The brute-force approach may fail for large input sizes. Repeated backward scans create quadratic work, so an online judge may report Time Limit Exceeded.
Complexity Analysis
Time Complexity: O(N2), an increasing price sequence makes every day scan all earlier days.
Space Complexity: O(1), only counters are used beyond the required output array.
Optimal Approach
The brute-force method checks many smaller prices again for different days. A decreasing stack avoids this repeated work by keeping only prices that can act as a greater boundary.
Prices smaller than or equal to the current price cannot stop the span, so their indices are removed. After removal, the stack top gives the nearest greater price on the left. If the stack becomes empty, it means all previous prices are less than or equal to the current price, so the span extends from the first day to the current day.
Algorithm
Create an empty stack to store indices of useful greater-price boundaries.
Create an answer array of size
Nto store the span for every day.Traverse the prices from left to right, so previously processed prices remain available for the current day.
Remove indices while the corresponding price is less than or equal to the current price, because such prices cannot stop the current span.
When the stack becomes empty, set the span to
currentDay + 1, because all prices to the left are less than or equal to the current price, so every day from index0tocurrentDaybelongs to the span.When the stack is not empty, set the span to
currentDay - stackTop, because the stack top is the nearest greater-price boundary.Push the current index so the current price can become a boundary for later days.
Return the completed answer array after processing all prices.
Dry Run
Stock Span Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Calculates every stock span with a monotonic stack. vector<int> calculateSpan(vector<int>& prices) { int n = prices.size(); vector<int> spans(n); stack<int> indices; // Earlier greater-price candidates stay on the stack. for (int currentDay = 0; currentDay < n; currentDay++) { // Smaller or equal prices cannot bound the span. while (!indices.empty() && prices[indices.top()] <= prices[currentDay]) { indices.pop(); } // An empty stack allows the span to reach day zero. if (indices.empty()) { spans[currentDay] = currentDay + 1; } else { // The nearest greater price on the left limits how far the span can extend. spans[currentDay] = currentDay - indices.top(); } indices.push(currentDay); } return spans; }};// Driver codeint main() { vector<int> prices = {100, 80, 60, 70, 60, 75, 85}; Solution obj; vector<int> spans = obj.calculateSpan(prices); for (int span : spans) cout << span << " "; return 0;}Complexity Analysis
Time Complexity: O(N), every index enters the stack once and leaves the stack at most once.
Space Complexity: O(N), the monotonic stack may store all indices for a strictly decreasing price sequence.
Interview follow-up Questions
Yes. The definition accepts earlier prices less than or equal to the current price, so equal-price indices must be popped by the optimal approach.
Be the first to add a comment.