C++ Solution with O(n) and O(nlog(n)^2)

• first solution is to do the reverse operation from the end of the day and update the left and right of the flower x. This is O(n)

``````class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
int n = flowers.size();
vector<int> vec;
for (auto v : flowers) vec.push_back(v);
sort(vec.begin(), vec.end());
vector<int> day(n + 1);
for (int i = 1; i <= flowers.size(); i++) {
day[flowers[i - 1]] = i;
}
int res = n + 1;
if (k == 0) res = n;
vector<int> left(n + 1, -1), right(n + 1, -1);
for (int i = 1; i <= n; i++) {
if (i > 1) left[i] = i - 1;
if (i < n) right[i] = i + 1;
}

for (int i = n - 1; i >= 0; i--) {
int v = flowers[i];
if (left[v] != -1 && right[v] != -1) {
if (k == right[v] - left[v] - 1) {
res = min(res, max(day[right[v]], day[left[v]]));
}
if (right[v] - v - 1 == k) {
res = min(res, i + 1);
}

if (v - left[v] - 1 == k) {
res = min(res, i + 1);
}
}
if (left[v] != -1) right[left[v]] = right[v];
if (right[v] != -1) left[right[v]] = left[v];
}
if (res == n + 1) res = -1;
return res;

}
};

``````

second solution is use binary indexed tree and binary search to find the left and right flower, this is O(nlog(n)^2)

``````class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
n = flowers.size();
c.resize(n + 10, 0);
for (int i = 1; i <= flowers.size(); i++) {
int v = flowers[i - 1];

int left = getLeft(v);
int right = getRight(v);

if (left != -1 && v - left - 1 == k) return  i;
if (right != -1 && right - v - 1== k) return i;

}
return -1;
}
private:
int n;
vector<int> c;
void add(int pos, int val) {
for (int i = pos; i <= n; i += i & -i)
c[i] += val;
}

int sum(int pos) {
int res = 0;
for (int i = pos; i; i -= i & -i)
res += c[i];
return res;
}

int getLeft(int v) {
int one = sum(v - 1);
if (one <= 0) return -1;
int l = 1, r = v - 1;
int left;
while (l <= r) {
int m = l + r >> 1;
int t = sum(m);
if (t < one) l = m + 1;
else {
if (sum(m) - sum(m - 1) == 1) {
left = m;
}
r = m - 1;
}
}
return left;
}

int getRight(int v) {
int one = sum(n) - sum(v);
if (one <= 0) return -1;
int l = v + 1, r = n;
int right;
while (l <= r) {
int m = l + r >> 1;
int t = sum(m) - sum(v);
if (t > 1) r = m - 1;
else if (t == 0) {
l = m + 1;
} else{
if (sum(m) - sum(m - 1) == 1) {
right = m;
}
r = m - 1;
}
}
return right;
}
};
``````

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