There is a garden with
N slots. In each slot, there is a flower. The
N flowers will bloom one by one in
N days. In each day, there will be
exactly one flower blooming and it will be in the status of blooming since then.
Given an array
flowers consists of number from
N. Each number in the array represents the place where the flower will open in that day.
flowers[i] = x means that the unique flower that blooms at day
i will be at position
x will be in the range from
Also given an integer
k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is
k and these flowers are not blooming.
If there isn't such day, output -1.
Input: flowers: [1,3,2] k: 1 Output: 2 Explanation: In the second day, the first and the third flower have become blooming.
Input: flowers: [1,2,3] k: 1 Output: -1
Let\'s add flowers in the order they bloom. When each flower blooms, we check it\'s neighbors to see if they can satisfy the condition with the current flower.\n
active, a sorted data structure containing every flower that has currently bloomed. When we add a flower to
active, we should check it\'s lower and higher neighbors. If some neighbor satisfies the condition, we know the condition occurred first on this day.
Time Complexity (Java): , where is the length of
flowers. Every insertion and search is .
Time Complexity (Python): . As above, except
list.insert is .
Space Complexity: , the size of
For each contiguous block ("window") of
k positions in the flower bed, we know it satisfies the condition in the problem statement if the minimum blooming date of this window is larger than the blooming date of the left and right neighbors.
Because these windows overlap, we can calculate these minimum queries more efficiently using a sliding window structure.\n
days[x] = i be the time that the flower at position
x blooms. For each window of
k days, let\'s query the minimum of this window in (amortized) constant time using a
MinQueue, a data structure built just for this task. If this minimum is larger than it\'s two neighbors, then we know this is a place where "
k empty slots" occurs, and we record this candidate answer.
To operate a
MinQueue, the key invariant is that
mins will be an increasing list of candidate answers to the query
For example, if our queue is
[1, 3, 6, 2, 4, 8], then
mins will be
[1, 2, 4, 8]. As we
mins will become
[2, 4, 8], then after 3 more
popleft\'s will become
[4, 8], then after 1 more
popleft will become
MinQueue.append, we should maintain this invariant. We do it by popping any elements larger than the one we are inserting. For example, if we appended
[1, 3, 6, 2, 4, 8], then
mins which was
[1, 2, 4, 8] becomes
[1, 2, 4, 5].
Note that we used a simpler variant of
MinQueue that requires every inserted element to be unique to ensure correctness. Also, the operations are amortized constant time because every element will be inserted and removed exactly once from each queue.
Time Complexity: , where is the length of
flowers. In enumerating through the outer loop, we do constant work as
MinQueue.min operations are (amortized) constant time.
Space Complexity: , the size of our
As in Approach #2, we have
days[x] = i for the time that the flower at position
x blooms. We wanted to find candidate intervals
[left, right] where
days[left], days[right] are the two smallest values in
[days[left], days[left+1], ..., days[right]], and
right - left = k + 1.
Notice that these candidate intervals cannot intersect: for example, if the candidate intervals are
[left1, right1] and
[left2, right2] with
left1 < left2 < right1 < right2, then for the first interval to be a candidate,
days[left2] > days[right1]; and for the second interval to be a candidate,
days[right1] > days[left2], a contradiction.
That means whenever whether some interval can be a candidate and it fails first at
j < i can\'t be the start of a candidate interval. This motivates a sliding window approach.
As in Approach #2, we construct
Then, for each interval
[left, right] (starting with the first available one), we\'ll check whether it is a candidate: whether
days[i] > days[left] and
days[i] > days[right] for
left < i < right.
If we fail, then we\'ve found some new minimum
days[i] and we should check the new interval
[i, i+k+1]. If we succeed, then it\'s a candidate answer, and we\'ll check the new interval