Simple simulation


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


  • 1
    Z

    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.


  • 1

    @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


  • 0

    @StefanPochmann Haha, faster than my BIT solution, which takes 653ms...


  • 0

    @BigBiang What is "BIT" short for? I have seen this term several times and searched in Google but got no results. Thanks in advance.


  • 0

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


  • 0

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


Log in to reply
 

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