# Using Segment tree

• ``````class Solution {
vector <int> segmentTree;
int n;

void initSegmentTree(int N) {
int length = 2 * pow(2.0, floor(log((double) N) / log(2.0)) + 1 );
segmentTree.resize(length, 0);
}

int query(int node, int left, int right, const int lower, const int upper) {
if(lower > right or upper < left) {
return 0;
}

if(left >= lower and right <= upper) {
return segmentTree[node];
}

int mid = left + (right - left) / 2;
int leftIndx = node << 1, rightIndx = leftIndx | 1;

return query(leftIndx, left, mid, lower, upper) + query(rightIndx, mid + 1, right, lower, upper);
}

int query(int lower, int upper) {
return query(1, 0, n - 1, lower, upper);
}

int update(int node, int left, int right, const int indx) {
if(indx < left or indx > right or left > right) {
return 0;
}

if(left == right) {
return ++segmentTree[node];
}
int mid = left + (right - left) / 2;
int leftIndx = node << 1, rightIndx = leftIndx | 1;

return segmentTree[node] = update(leftIndx, left, mid, indx) + update(rightIndx, mid + 1, right, indx);
}

void update(int indx) {
update(1, 0, n - 1, indx);
}
public:
int kEmptySlots(vector<int>& flowers, int k) {
n = flowers.size();
initSegmentTree(n);
vector<bool> bloom(n, false);
for(int i = 0; i < n; i++) {
flowers[i]--;
bloom[flowers[i]] = true;
update(flowers[i]);

int left = max(flowers[i] - k, 0);
int right = max(flowers[i] - 1, 0);
if(left > 0 and query(left, right) == 0 and bloom[left - 1]) {
return i + 1;
}

left = min(flowers[i] + 1, n - 1);
right = min(flowers[i] + k, n - 1);
if(right < n - 1 and query(left, right) == 0 and bloom[right + 1]) {
return i + 1;
}
}
return -1;
}
};
``````

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