Problems › JavaScript › patterns
How long this price has held up
A trading widget shows, for each day, how many days back the price has been no higher than it is today — today included.
- Count today and then each earlier consecutive day whose price is less than or equal to today’s.
- Stop at the first earlier day priced above today.
- The first day always answers 1.
priceRun(prices: list<int>) → list<int>
Where you start
function priceRun(prices) {
}Worked examples
| Call | Result |
|---|---|
priceRun([100,80,60,70,60,75,85]) | [1,1,1,2,1,4,6] |
priceRun([10,20,30]) | [1,2,3] |
priceRun([30,20,10]) | [1,1,1] |
priceRun([5,5,5]) | [1,2,3] |
Hint
Rather than walking backwards each day, keep a stack of earlier days that were priced higher. Popping the ones that were not gives you the run in one pass.
Reference solution in JavaScript
function priceRun(prices) {
const runs = [];
const higher = [];
for (let i = 0; i < prices.length; i += 1) {
while (higher.length > 0 && prices[higher[higher.length - 1]] <= prices[i]) higher.pop();
runs.push(higher.length === 0 ? i + 1 : i - higher[higher.length - 1]);
higher.push(i);
}
return runs;
}