KEmptySlotsBIT.java

class Solution {
	// Binary index tree is 1 indexed
	private int[] bitree;	
	
	public int kEmptySlots(int[] flowers, int k) {
		int len = flowers.length; 
		bitree = new int[len + 1];
		
		for (int i = 0; i < len; i++) {
			update(1, flowers[i]);
			
			// Compare the flower k distance apart to its right
			if (flowers[i] + k + 1 <= len) {
				if (read(flowers[i] + k + 1) - read(flowers[i]) == 1) {
					return i + 1; 
				}
			}
			
			// Compare the flower k distance apart to its left
			if (flowers[i] - k - 1 >= 1) {
				if (read(flowers[i]) - read(flowers[i] - k - 1) == 1) {
					return i + 1;
				}
			}
		}
		
		return -1; 
	}
	
	/*
	 * Binary index tree update method. 
	 * It adds given value to the given node and all 
	 * the nodes that "cover" it. 
	 */
	private void update(int val, int index) {
		while (index < bitree.length) {
			bitree[index] += val; 
			index += index & (-index);
		}
	}
	
	/*
	 * Binary index tree read method. 
	 * It returns the prefix sum of a given index.
	 */
	private int read(int index) {
		int sum = 0; 
		
		while (index > 0) {
			sum += bitree[index];
			index -= index & (-index);
		}
		
		return sum; 
	}
}