https://leetcode.com/problems/k-empty-slots/

Solution

We can come up with a naive solution:

  • let a is array store the state of bulks, a[i] = 1/0 ie bulk i is on/off
  • for each day we update a[bulk[i]] = 1
  • we need to find in a a subarray of len k+2 with sum == k, if such subarray exists => break and return. We can find this subarray by prefix sum s[i] = sum(a[0]...a[i])

Runtime O(n^2)

One thing we can notice is for each day, when we turn on bulk i, we only need to care about its next on bulk and previous on bulk. In other word, we need to somehow quickly find out the prev less number and next bigger number => use set

  • to find next bigger number of bulk[i], we use upper_bound, which return the iterator point to the first number > bulk[i]
set<int>::iterator next = pos.upper_bound(bulk[i]);
  • to find previous less number of bulk[i], we use lower_bound, which return the iterator point to the first number >= bulk[i] => the previous less number should be *(--prev)
set<int>::iterator prev = --pos.lower_bound(bulk[i]);

This technique is important and being used in multiple problems.

    int kEmptySlots(vector<int>& a, int K) {
        set<int> pos;
        int n = a.size();
        pos.insert(a[0]);
        for(int i = 1; i < n; i++) {
            set<int>::iterator next = pos.upper_bound(a[i]);
            if (next != pos.end() && *next - a[i] == K+1) return i+1;
            set<int>::iterator prev = pos.lower_bound(a[i]);
            
            if (prev != pos.begin()) {
                prev--;
                if (a[i] - *prev == K+1) return i+1;
            }
            pos.insert(a[i]);
        }
        return -1;
    }

Runtime: O(nlogn)

Leetcode has 2 more better solution, but I am too lazy to read it (as they are long).