Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

683. K Empty Slots

Time: $O(n)$

Space: $O(n)$

			


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;
  }
};




			


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;
  }
}




			


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