K Empty Slots_1.cpp

class Solution {
public:
    int kEmptySlots(vector<int>& flowers, int k) {
        int n = flowers.size();
        //days[i] represent the day when flower at i blooms
        vector<int> days(n, -1);
        for(int i = 0; i < n; ++i)
        {
            int idx = flowers[i];
            days[idx - 1] = i + 1;
        }
        int left = 0, right = k + 1, res = n + 1, i = 1;
        while(i < n)
        {
            if(right >= n)break;
            int day = days[i];
            if(i == right)
            {
                res = min(max(days[left], days[right]), res);
                left = i;
                right = i + k + 1;
            }
            //bug: use else if instead of if since when we arrive at right, the condition below might still be true
            else if(day < days[left] || day < days[right])
            {
                left = i;
                right = i + k + 1;
            }
            ++i;
        }
        return res == n + 1? -1 : res;
    }
};