# 683. K Empty Slots

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: int kEmptySlots(vector& bulbs, int k) { const int n = bulbs.size(); int ans = INT_MAX; // day[i] := the day when bulbs[i] is turned on vector 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 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