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 0-indexed and x is 1-indexed.
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 <= 200001 <= bulbs[i] <= Nbulbsis a permutation of numbers from1toN.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 := 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 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 }