Using Segment tree


  • 0
    K
    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;
        }
    };
    

Log in to reply
 

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