Find earliest time for k empty group

Question

I was asked this question in an interview recently, I still cannot come up with a solution.

There are N slots in a river. An array P is given where each index denotes the time at which the stone at that position will appear. I have to come up with an algorithm to find the earliest time at which there will be K contiguous empty slots. For E.G.

N = 5

P = [2,5,1,4,3]

K = 2

Initially: [0,0,0,0,0] 

All the slots are empty.

Now at:

Time t = 1, second stone will appear --> [0,1,0,0,0]

Time t = 2, fifth stone will appear --> [0,1,**0,0**,1]

Time t = 3, first stone will appear --> [1,1,0,0,1]

Time t = 4, fourth stone will appear --> [1,1,0,1,1]

Time t = 5, third stone will appear --> [1,1,1,1,1]

So the answer for above case is 2, because at time 2 there are (k = 2) continuous empty slots.

Answer 1

I finally found the O(n) time complexity and O(n) space complexity solution on leetcode. To explain briefly:

The idea is to use an array days[] to record each position flower's blooming day. That means days[i] is the blooming day of the flower in position i+1. We just need to find a subarray days[left, left+1,...,left+k-1, right] which satisfies: for any i = left+1,..., left+k-1, we can have days[left] < days[i] && days[right] < days[i]. Then, the result is max(days[left], days[right]).

Here is the link to the exact solution: https://discuss.leetcode.com/topic/104771/java-c-simple-o-n-solution