Straightforward and fast C++ solution (95.95%)


  • 0

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

Log in to reply
 

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