# Simple simulation

• ``````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.

• @BigBiang I should finally re-learn and practice BITs. But as long as list insertion is fast enough, I'm lacking the motivation :-P

• @songzy12 binary index tree. It supports to get sum and update a node in tree for O(logn) time.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.