BiruLyu
9/24/2017 - 3:17 PM

683. K Empty Slots(BITree).java

class BITree {
    int[] tree;
    int len;
    public BITree(int len) {
        tree = new int[len + 1];
        this.len = len;
    }
    public void update(int idx, int val) {
        idx++;
        while (idx <= len) {
            tree[idx] += val;
            idx += idx & (-idx);
        }
    }
    public int get(int idx) {
        int sum = 0;
        idx++;
        while (idx > 0) {
            sum += tree[idx];
            idx -= idx & (-idx);
        }
        return sum;
    }
}
public class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        int n = flowers.length;
        BITree bit = new BITree(n);
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int idx = flowers[i] - 1;
            set.add(idx);
            bit.update(idx, 1);
            if (set.contains(idx - k - 1) && bit.get(idx) - bit.get(idx - k - 2) == 2) {
                return i + 1;
            } else if (set.contains(idx + k + 1) && bit.get(idx + k + 1) - bit.get(idx - 1) == 2) {
                return i + 1;
            }
        }
        return -1;
    }
}