With explanation, binary index tree solution, O(nlogn)


  • 3

    I assume you already know the basic concept of BIT, and its two operations: getSum and update. I use a set bloomed to record the index of bloomed flowers, and update the binary index tree. Then everyday I check if the kth flower on the right hand side and on the left hand side has bloomed, and there is no flower between them has bloomed: getSum(index) == getSum(index - k - 1) or getSum(index) == getSum(index + k + 1) - 1. One thing need to notice is that if you check before updating the tree, you need to have that - 1 when checking the right hand side.

    class BITree(object):
        def __init__(self, n):
            self.node = [0 for _ in range(n + 1)]
        
        def getSum(self, index):
            index += 1
            result = 0
            while index > 0:
                result += self.node[index]
                index -= index & -index
            return result
        
        def update(self, index, d):
            index += 1
            while index < len(self.node):
                self.node[index] += d
                index += index & -index
                
    class Solution(object):
        def kEmptySlots(self, flowers, k):
            """
            :type flowers: List[int]
            :type k: int
            :rtype: int
            """
            bitree = BITree(len(flowers))
            bloomed = set()        
            for day, index in enumerate(flowers):
                index -= 1
                if index - k - 1 in bloomed and bitree.getSum(index) == bitree.getSum(index - k - 1):
                    return day + 1
                elif index + k + 1 in bloomed and bitree.getSum(index) + 1 == bitree.getSum(index + k + 1):
                    return day + 1
                else:
                    bloomed.add(index)
                    bitree.update(index, 1)
            return -1
    

  • 0
    F

    Brilliant solution. I've thought of BIT but haven't got a very clear idea. For saving time in OJ, I switched to TreeSet


Log in to reply
 

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