Skip to content

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<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 each 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 each 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 each 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