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 theminimum day number such that there exists two turned on bulbs that have exactlyk bulbs between them that are
all turned off. If there isn’t such day, return -1.
Input: bulbs =[1,3,2], k =1Output: 2Explanation:
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 return2 because on the second day, there were two on bulbs with one off bulb between them.
We want to find the earliest day when there are exactly k bulbs off between two bulbs that are on, and no other bulbs in between are on. By simulating the process and maintaining the positions of bulbs that are on in an ordered set, we can efficiently check the required condition for each day.
classSolution {
public:int kEmptySlots(vector<int>& bulbs, int k) {
int n = bulbs.size();
vector<int> days(n);
for (int i =0; i < n; ++i) days[bulbs[i] -1] = i +1;
int ans = INT_MAX;
int left =0, right = k +1;
while (right < n) {
bool valid = true;
for (int i = left +1; i < right; ++i) {
if (days[i] < days[left] || days[i] < days[right]) {
left = i;
right = left + k +1;
valid = false;
break;
}
}
if (valid) {
ans = min(ans, max(days[left], days[right]));
left = right;
right = left + k +1;
}
}
return ans == INT_MAX ?-1: ans;
}
};
classSolution {
publicintkEmptySlots(int[] bulbs, int k) {
int n = bulbs.length;
int[] days =newint[n];
for (int i = 0; i < n; ++i) days[bulbs[i]- 1]= i + 1;
int ans = Integer.MAX_VALUE;
int left = 0, right = k + 1;
while (right < n) {
boolean valid =true;
for (int i = left + 1; i < right; ++i) {
if (days[i]< days[left]|| days[i]< days[right]) {
left = i;
right = left + k + 1;
valid =false;
break;
}
}
if (valid) {
ans = Math.min(ans, Math.max(days[left], days[right]));
left = right;
right = left + k + 1;
}
}
return ans == Integer.MAX_VALUE?-1 : ans;
}
}
classSolution {
funkEmptySlots(bulbs: IntArray, k: Int): Int {
val n = bulbs.size
val days = IntArray(n)
for (i in bulbs.indices) days[bulbs[i] - 1] = i + 1var ans = Int.MAX_VALUE
var left = 0var right = k + 1while (right < n) {
var valid = truefor (i in left + 1 until right) {
if (days[i] < days[left] || days[i] < days[right]) {
left = i
right = left + k + 1 valid = falsebreak }
}
if (valid) {
ans = minOf(ans, maxOf(days[left], days[right]))
left = right
right = left + k + 1 }
}
returnif (ans ==Int.MAX_VALUE) -1else ans
}
}
defk_empty_slots(bulbs: list[int], k: int) -> int:
n = len(bulbs)
days = [0] * n
for i, b in enumerate(bulbs):
days[b-1] = i +1 ans = float('inf')
left, right =0, k +1while right < n:
valid =Truefor i in range(left +1, right):
if days[i] < days[left] or days[i] < days[right]:
left = i
right = left + k +1 valid =Falsebreakif valid:
ans = min(ans, max(days[left], days[right]))
left = right
right = left + k +1return-1if ans == float('inf') else ans
fnk_empty_slots(bulbs: Vec<i32>, k: i32) -> i32 {
let n = bulbs.len();
letmut days =vec![0; n];
for (i, &b) in bulbs.iter().enumerate() {
days[b asusize-1] = i asi32+1;
}
letmut ans =i32::MAX;
let (mut left, mut right) = (0, k +1);
while (right asusize) < n {
letmut valid =true;
for i in (left +1)..right {
if days[i asusize] < days[left asusize] || days[i asusize] < days[right asusize] {
left = i;
right = left + k +1;
valid =false;
break;
}
}
if valid {
ans = ans.min(days[left asusize].max(days[right asusize]));
left = right;
right = left + k +1;
}
}
if ans ==i32::MAX { -1 } else { ans }
}