InternDoor

How far back is it the best?

Mediumstack · monotonic stack · arrays

Reported in interviews at (where)

prices[d] is a share's price on day d. The span of a day is how many days in a row, ending with that day and going back, had a price no higher than that day's price. A day always counts itself.

Return the span of every day, in order.

Example 1
Input
prices = [30,25,27,27,40,10]
Output
[1,1,2,3,5,1]

The second 27 looks back over 27 and 25 before 30 stops it; 40 is higher than everything before it.

Example 2
Input
prices = [5,5,5]
Output
[1,2,3]

An equal price does not stop the count.

Limits

  • 1 <= prices.length <= 100000
  • 1 <= prices[d] <= 100000

Hints

Hint 1

Keep a stack of days whose price is still the highest seen since them.

Hint 2

Pop every day that is no higher than today: today now covers them.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.