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;
}
}