K Empty Slots


Also, we can use somthing like bucket algorithm. Create buckets of k elements, and split all n values between this buckets. Each bucket should store min_left and max_right blooming index. So, at the beginning there are no blooming flowers in buckets. Each day we just set index in bucket (update values if it is needed). And check left and right bucket. O(n/k) additional memory and O(n) time.

To implement a min queue you can also use 2 stacks which is also amortized linear time. See https://stackoverflow.com/questions/4802038/implementaqueueinwhichpushrearpopfrontandgetminareallconsta

@littlefinzer Thanks for bringing it to my attention. I will update the article in the next couple of days.

@Arkkun I think somewhere in the forum people already talked about this. You need to output the first day this event occurs, hence expected out put = 6 in your example.

@alexandr2017
After 1st day:_ _ X _ _ _ _ _ _ _
After 2nd day:_ _ X _ _ _ _ _ X _
...
After 5th day:X X X _ _ _ _ X X _
After 6th day:X X X _ _ X _ X X _
, satisfies the condition (theres K=1 unbloomed between bloomed at positions 6, 8)