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

## C++

``````class Solution {
public:
int kEmptySlots(vector<int>& bulbs, int k) {
const int n = bulbs.size();
int ans = INT_MAX;
// day[i] := the day when bulbs[i] is turned on
vector<int> day(n);

for (int i = 0; i < n; ++i)
day[bulbs[i] - 1] = i + 1;

// find a subarray of day[l..r], where its length is k + 2
// for all that l < i < r, day[i] > max(day[l], day[r])
int l = 0;
int r = l + k + 1;
for (int i = 1; r < n; ++i)
if (i == r) {
ans = min(ans, max(day[l], day[r]));
l = i;
r = i + k + 1;
} else if (day[i] < max(day[l], day[r])) {
l = i;
r = i + k + 1;
}

return ans == INT_MAX ? -1 : ans;
}
};
``````

## JAVA

``````class Solution {
public int kEmptySlots(int[] bulbs, int k) {
final int n = bulbs.length;
int ans = Integer.MAX_VALUE;
// day[i] := the day when bulbs[i] is turned on
int[] day = new int[n];

for (int i = 0; i < n; ++i)
day[bulbs[i] - 1] = i + 1;

// find a subarray of day[l..r], where its length is k + 2
// for all that l < i < r, day[i] > max(day[l], day[r])
int l = 0;
int r = l + k + 1;
for (int i = 1; r < n; ++i)
if (i == r) {
ans = Math.min(ans, Math.max(day[l], day[r]));
l = i;
r = i + k + 1;
} else if (day[i] < Math.max(day[l], day[r])) {
l = i;
r = i + k + 1;
}

return ans == Integer.MAX_VALUE ? -1 : ans;
}
}
``````

## Python

``````class Solution:
def kEmptySlots(self, bulbs: List[int], k: int) -> int:
n = len(bulbs)
ans = math.inf
# day[i] := the day when bulbs[i] is turned on
day = [0] * n

for i, bulb in enumerate(bulbs):
day[bulb - 1] = i + 1

# find a subarray of day[l..r], where its length is k + 2
# for all that l < i < r, day[i] > max(day[l], day[r])
l = 0
r = l + k + 1
i = 1
while r < n:
if i == r:
ans = min(ans, max(day[l], day[r]))
l = i
r = i + k + 1
elif day[i] < max(day[l], day[r]):
l = i
r = i + k + 1
i += 1

return -1 if ans == math.inf else ans
``````