Problem statement

https://leetcode.com/problems/k-empty-slots/

Solution 1

One of the possible solutions is to use BIT or segment tree: when i-th flower is open we can keep states as zeros and ones. We update states for each flower and check next k flowers and previous k flowers.

Complexity

Time complexity of one update is O(log n), so overall time complexity is O(n log n) and space complexity is O(n).

Code

class BIT:
    def __init__(self, n):
        self.sums = [0] * (n+1)
    
    def update(self, i, delta):
        while i < len(self.sums):
            self.sums[i] += delta
            i += i & (-i)
    
    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res
        
    def sum(self, i,j):
        return self.query(j) - self.query(i-1)
        
class Solution:
    def kEmptySlots(self, flowers, k):
        n = len(flowers)
        bit, arr = BIT(n), [0]*(n+1)
        
        for i, num in enumerate(flowers):
            bit.update(num, 1)
            arr[num] = 1

            if num > k+1 and arr[num-k-1] == 1 and bit.sum(num-k, num-1) == 0:
                return i + 1
            if num+k+1 <= n and arr[num+k+1] == 1 and bit.sum(num+1, num+k) == 0:
                return i + 1

        return -1

Solution 2

There is also O(n) solution, using sliding window: we create inverse array of days: for each place we evaluate day when on these place flower will blossom and then we use sliding window of size k+1. The trick is that our windows can not intersect! Also if we meet number less then ends of our window, we need to move our window and it can be shown that we need to move its start to i-th place.

Complexity

Code

class Solution:
    def kEmptySlots(self, flowers, k):
        n, left, right, res = len(flowers), 0, k+1, float("inf")
        days = [0]*n
        for i in range(n):
            days[flowers[i]-1] = i+1
            
        for i in range(n):
            if right >= n: break
            if days[i] < days[left] or days[i] <= days[right]:
                if i == right: res = min(res, max(days[left], days[right]))
                left, right = i, k + i + 1
                
        return -1 if res == float("inf") else res