Straightforward and fast C++ solution (95.95%)

• The solution I wrote is like a brute force solution. I was surprised it is relative fast among current submissions. The idea is simple, walk through the `flowers` array and mark the `bloom` array for the corresponding day. Before setting the day to true, checking left and right to see whether there exist a "K empty slots".

``````class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
int n = flowers.size();
if (n < k + 2) return -1;
vector<bool> bloom(n, false);

for (int i = 0; i < n; i++) {
int pos = flowers[i] - 1; // bloom position as the array index
int idx = pos - 1;
/* loop invariance, idx point to non-bloom positions to the left of pos. */
while (pos - k - 1 >= 0 && idx > pos - k - 1 && !bloom[idx]) {
idx--;
}
/* if there is a solution in the left, idx must point to the first bloom
* position to the left of pos and there are exactly k non-bloom position in between */
if (idx == pos - k - 1 && bloom[idx]) {
return i + 1;
}

idx = pos + 1;
while (pos + k + 1 < n && idx < pos + k + 1 && !bloom[idx]) {
idx++;
}
if (idx == pos + k + 1 && bloom[idx]) {
return i + 1;
}

/* must set current bloom to true at last */
bloom[pos] = true;
}

return -1;
}
};
``````

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