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>
C# needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
public List<int> PriceRun(List<int> prices) {
}Worked examples
| Call | Result |
|---|---|
PriceRun(new List<int> { 100, 80, 60, 70, 60, 75, 85 }) | new List<int> { 1, 1, 1, 2, 1, 4, 6 } |
PriceRun(new List<int> { 10, 20, 30 }) | new List<int> { 1, 2, 3 } |
PriceRun(new List<int> { 30, 20, 10 }) | new List<int> { 1, 1, 1 } |
PriceRun(new List<int> { 5, 5, 5 }) | new List<int> { 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 C#
public List<int> PriceRun(List<int> prices) {
var runs = new List<int>();
var higher = new Stack<int>();
for (int i = 0; i < prices.Count; i++) {
while (higher.Count > 0 && prices[higher.Peek()] <= prices[i]) higher.Pop();
runs.Add(higher.Count == 0 ? i + 1 : i - higher.Peek());
higher.Push(i);
}
return runs;
}