Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/683.html
683. K Empty Slots
Level
Hard
Description
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 everyday 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 0indexed and x
is 1indexed
.
Given an integer K
, find out 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
.
Example 1:
Input:
bulbs: [1,3,2]
K: 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.
Example 2:
Input:
bulbs: [1,2,3]
K: 1
Output: 1
Note:
1 <= N <= 20000
1 <= bulbs[i] <= N
bulbs
is a permutation of numbers from1
toN
.0 <= K <= 20000
Solution
Create a class Interval
that represents continuous intervals of turned off bulbs. Each object of Interval
has data fields start
and end
that represents the start position and the end position. The intervals are compared according to start
in ascending order and then according to end
in ascending order.
Maintain a map that stores each day and the index of the bulb that is turned on. Also maintain a tree set to store the intervals, where the intervals are sorted in ascending order. Initially, the tree set contains a single interval [1, N]
. On the first day, since only one bulb is turned on, there do not exist two bulbs that are turned on, so simply update the tree set after the first bulb is turned on. After the first day, the tree set man contain one interval or two intervals. From the second day, each day obtain the maximum interval that has start
less than or equal to the current bulb’s index, which contains the current bulb’s index. It is guaranteed that such an interval exists, since all turned off bulbs are in the intervals.
If the current bulb’s index equals the start of the interval or the end of the interval, then if K
is 0 and the bulb is not at any end of the row (that is, the bulb is not at index 1 or index N
), return the current day. Otherwise, remove the previous interval and add one new interval to the tree set.
If the current bulb’s index is in the middle of the interval (not at the start or the end of the interval), then the current interval will be split after the current bulb is turned on. Check the two intervals. If one interval has length K
and its start position is not 1 and its end position is not N
, then return the current day. Otherwise, remove the previous interval and add two new intervals to the tree set.
If an interval of length K
that is not at the start or the end of the row is found, return 1.

class Solution { public int kEmptySlots(int[] bulbs, int K) { Map<Integer, Integer> dayIndexMap = new HashMap<Integer, Integer>(); int length = bulbs.length; for (int i = 0; i < length; i++) dayIndexMap.put(i + 1, bulbs[i]); TreeSet<Interval> set = new TreeSet<Interval>(); int bulb1 = bulbs[0]; if (bulb1 == 1) set.add(new Interval(2, length)); else if (bulb1 == length) set.add(new Interval(1, length  1)); else { set.add(new Interval(1, bulb1  1)); set.add(new Interval(bulb1 + 1, length)); } for (int i = 1; i < length; i++) { int day = i + 1; int bulb = bulbs[i]; Interval curr = set.floor(new Interval(bulb, length)); set.remove(curr); if (curr.start == bulb) { if (K == 0 && bulb > 1) return day; else if (curr.end < length && curr.end  bulb == K) return day; else set.add(new Interval(bulb + 1, curr.end)); } else if (curr.end == bulb) { if (K == 0 && bulb < length) return day; else if (curr.start > 1 && bulb  curr.start == K) return day; else set.add(new Interval(curr.start, bulb  1)); } else { if (curr.start > 1 && bulb  curr.start == K  curr.end < length && curr.end  bulb == K) return day; else { set.add(new Interval(curr.start, bulb  1)); set.add(new Interval(bulb + 1, curr.end)); } } } return 1; } } class Interval implements Comparable<Interval> { int start; int end; public Interval(int start, int end) { this.start = start; this.end = end; } public int compareTo(Interval interval2) { if (this.start != interval2.start) return this.start  interval2.start; else return this.end  interval2.end; } public boolean equals(Object obj) { if (obj instanceof Interval) { Interval interval2 = (Interval) obj; return this.start == interval2.start && this.end == interval2.end; } else return false; } }

class BinaryIndexedTree: def __init__(self, n): self.n = n self.c = [0] * (n + 1) @staticmethod def lowbit(x): return x & x def update(self, x, delta): while x <= self.n: self.c[x] += delta x += BinaryIndexedTree.lowbit(x) def query(self, x): s = 0 while x > 0: s += self.c[x] x = BinaryIndexedTree.lowbit(x) return s class Solution: def kEmptySlots(self, bulbs: List[int], k: int) > int: n = len(bulbs) tree = BinaryIndexedTree(n) for i, x in enumerate(bulbs, 1): tree.update(x, 1) case1 = ( x  k  1 > 0 and tree.query(x  k  1)  tree.query(x  k  2) == 1 and tree.query(x  1)  tree.query(x  k  1) == 0 ) case2 = ( x + k + 1 <= n and tree.query(x + k + 1)  tree.query(x + k) == 1 and tree.query(x + k)  tree.query(x) == 0 ) if case1 or case2: return i return 1

class BinaryIndexedTree { public: int n; vector<int> c; BinaryIndexedTree(int _n) : n(_n) , c(_n + 1) {} void update(int x, int delta) { while (x <= n) { c[x] += delta; x += lowbit(x); } } int query(int x) { int s = 0; while (x > 0) { s += c[x]; x = lowbit(x); } return s; } int lowbit(int x) { return x & x; } }; class Solution { public: int kEmptySlots(vector<int>& bulbs, int k) { int n = bulbs.size(); BinaryIndexedTree* tree = new BinaryIndexedTree(n); for (int i = 0; i < n; ++i) { int x = bulbs[i]; tree>update(x, 1); bool case1 = x  k  1 > 0 && tree>query(x  k  1)  tree>query(x  k  2) == 1 && tree>query(x  1)  tree>query(x  k  1) == 0; bool case2 = x + k + 1 <= n && tree>query(x + k + 1)  tree>query(x + k) == 1 && tree>query(x + k)  tree>query(x) == 0; if (case1  case2) return i + 1; } return 1; } };

type BinaryIndexedTree struct { n int c []int } func newBinaryIndexedTree(n int) *BinaryIndexedTree { c := make([]int, n+1) return &BinaryIndexedTree{n, c} } func (this *BinaryIndexedTree) lowbit(x int) int { return x & x } func (this *BinaryIndexedTree) update(x, delta int) { for x <= this.n { this.c[x] += delta x += this.lowbit(x) } } func (this *BinaryIndexedTree) query(x int) int { s := 0 for x > 0 { s += this.c[x] x = this.lowbit(x) } return s } func kEmptySlots(bulbs []int, k int) int { n := len(bulbs) tree := newBinaryIndexedTree(n) for i, x := range bulbs { tree.update(x, 1) case1 := xk1 > 0 && tree.query(xk1)tree.query(xk2) == 1 && tree.query(x1)tree.query(xk1) == 0 case2 := x+k+1 <= n && tree.query(x+k+1)tree.query(x+k) == 1 && tree.query(x+k)tree.query(x) == 0 if case1  case2 { return i + 1 } } return 1 }