Golang solution using Binary Indexed Tree


  • 0

    Pretty much same idea as this C++ solution.
    Both BIT and the question itself has index from 1 (not 0) which is quite error-prone...

    func kEmptySlots(flowers []int, k int) int {
    	bit, isBloom := make(BIT, len(flowers)+1), make([]int, len(flowers))
    	for i, f := range flowers {
    		f-- // adjut to (0..N)
    		add(bit, f, 1)
    		isBloom[f] = 1
    		if (f-k-1 >= 0 && isBloom[f-k-1] == 1 && sum(bit, f-1)-sum(bit, f-k-1) == 0) ||
    			(f+k+1 < len(flowers) && isBloom[f+k+1] == 1 && sum(bit, f+k)-sum(bit, f) == 0) {
    			return i + 1
    		}
    	}
    	return -1
    }
    
    type BIT []int
    
    func add(bit BIT, index, value int) {
    	for index = index + 1; index < len(bit); {
    		bit[index] += value
    		index += index & -index
    	}
    }
    
    func sum(bit BIT, index int) (sum int) {
    	for index = index + 1; index > 0; {
    		sum += bit[index]
    		index -= index & -index
    	}
    	return sum
    }
    

Log in to reply
 

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