683. K Empty Slots

You have n bulbs in a row numbered from 1 to n. Initially, all the bulbs are turned off. We turn on exactly one bulb every day until all bulbs are on after n days.

You are given an array bulbs of length n where bulbs[i] = x means that on the (i+1)th day, we will turn on the bulb at position x where i is 0-indexed and x is 1-indexed.

Given an integer k, return the minimum day number such that there exists two turned on bulbs that have exactly k bulbs between them that are all turned off. If there isn’t such day, return -1.

• fenwick tree solution
• Time : O(nlogn)
• Space : O(n)

class Solution {
    int fenwick[20001];
    void update(int index) {
        while(index <= 20000) {
            fenwick[index]++;
            index += index & -index;
        }
    }
    int qry(int index) {
        int res = 0;
        while(index > 0) {
            res += fenwick[index];
            index -= index & -index;
        }
        return res;
    }
    bool verify(int from, int to) {
        int on = qry(from) - qry(from - 1);
        if(on == 0) return false;
        on = qry(to) - qry(to - 1);
        if(on == 0) return false;
        return qry(to - 1) == qry(from);
    }
public:
    int kEmptySlots(vector<int>& bulb, int k) {
        for(int i = 0; i < bulb.size(); i++) {
            update(bulb[i]);
            if(bulb[i] - k - 1 >= 1) { //check front
                if(verify(bulb[i] - k - 1, bulb[i]))
                    return i + 1;
            }
            if(bulb[i] + k + 1 <= bulb.size()) {
                if(verify(bulb[i], bulb[i] + k + 1))
                    return i + 1;
            }
        }
        return -1;
    }
};

• Time : O(nlogn)
• Space : O(n)

class Solution {
public:
    int kEmptySlots(vector<int>& bulbs, int k) {
        set<int> onBulbs;
        for(int i = 0; i < bulbs.size(); i++) {
            auto cur = onBulbs.insert(bulbs[i]).first;
            if(cur != onBulbs.begin() and *prev(cur) == bulbs[i]-k-1) return i + 1;
            if(next(cur) != onBulbs.end() and *next(cur) == bulbs[i] + k + 1) return i + 1;
        }
        return -1;
    }
};