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>
Go 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
func priceRun(prices []int) []int {
}Worked examples
| Call | Result |
|---|---|
priceRun([]int{100, 80, 60, 70, 60, 75, 85}) | []int{1, 1, 1, 2, 1, 4, 6} |
priceRun([]int{10, 20, 30}) | []int{1, 2, 3} |
priceRun([]int{30, 20, 10}) | []int{1, 1, 1} |
priceRun([]int{5, 5, 5}) | []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 Go
func priceRun(prices []int) []int {
runs := []int{}
higher := []int{}
for i, price := range prices {
for len(higher) > 0 && prices[higher[len(higher)-1]] <= price {
higher = higher[:len(higher)-1]
}
if len(higher) == 0 {
runs = append(runs, i+1)
} else {
runs = append(runs, i-higher[len(higher)-1])
}
higher = append(higher, i)
}
return runs
}