def kEmptySlots(self, flowers, k): blooming =  for day, flower in enumerate(flowers, 1): i = bisect.bisect(blooming, flower) for neighbor in blooming[i-(i>0):i+1]: if abs(flower - neighbor) - 1 == k: return day blooming.insert(i, flower) return -1
Keep track of the already blooming flowers with a sorted list. When adding a flower, check how far away its already blooming neighbors are.
However, inserting numbers to a sorted list costs O(n), which means this algorithm is worst case O(n^2). And for n < 20000, this is a dangerously slow algorithm.
@zhudhjen Yeah, true. But the insertion's O(n) is a very fast O(n), since it's implemented in C and only has to simply shift data, nothing complicated. In practice, at least on LeetCode, it appears to be comparable to the O(log n) of a self-made tree written in Python. I think the first time I used this was exactly because such an O(log n) was too slow, everybody had problems getting any Python solution accepted, but with a list and its O(n) insertion it was fast enough. Anyway, here it gets accepted in about 600 ms, and the time limit I think is usually 2000 ms.
Edit: Found that old one again: https://discuss.leetcode.com/topic/49933/python-o-n-4-solution
@StefanPochmann Haha, faster than my BIT solution, which takes 653ms...
@BigBiang What is "BIT" short for? I have seen this term several times and searched in Google but got no results. Thanks in advance.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.