K Empty Slots

hard array sliding window

Problem

Bulbs[i] tells the position bloomed on day i+1. Return earliest day where two bulbs have exactly k empty slots between them, both bloomed.

Inputbulbs=[1,3,2] k=1

Output2

On day 2 positions {1,3} bloomed; one empty between them.

input

def k_empty_slots(bulbs, k):
    n = len(bulbs); days = [0] * n
    for d, p in enumerate(bulbs): days[p - 1] = d + 1
    best = 10**9; l, r = 0, k + 1
    while r < n:
        ok = True
        for i in range(l + 1, r):
            if days[i] < days[l] or days[i] < days[r]: l = i; r = i + k + 1; ok = False; break
        if ok: best = min(best, max(days[l], days[r])); l = r; r = l + k + 1
    return best if best < 10**9 else -1

function kEmptySlots(bulbs, k) {
  const n = bulbs.length; const days = new Array(n).fill(0);
  for (let d = 0; d < n; d++) days[bulbs[d] - 1] = d + 1;
  let best = Infinity, l = 0, r = k + 1;
  while (r < n) {
    let ok = true;
    for (let i = l + 1; i < r; i++) {
      if (days[i] < days[l] || days[i] < days[r]) { l = i; r = i + k + 1; ok = false; break; }
    }
    if (ok) { best = Math.min(best, Math.max(days[l], days[r])); l = r; r = l + k + 1; }
  }
  return isFinite(best) ? best : -1;
}

int kEmptySlots(int[] bulbs, int k) {
    int n = bulbs.length; int[] days = new int[n];
    for (int d = 0; d < n; d++) days[bulbs[d] - 1] = d + 1;
    int best = Integer.MAX_VALUE, l = 0, r = k + 1;
    while (r < n) {
        boolean ok = true;
        for (int i = l + 1; i < r; i++) if (days[i] < days[l] || days[i] < days[r]) { l = i; r = i + k + 1; ok = false; break; }
        if (ok) { best = Math.min(best, Math.max(days[l], days[r])); l = r; r = l + k + 1; }
    }
    return best == Integer.MAX_VALUE ? -1 : best;
}

int kEmptySlots(vector& bulbs, int k) {
    int n = bulbs.size(); vector days(n);
    for (int d = 0; d < n; d++) days[bulbs[d] - 1] = d + 1;
    int best = INT_MAX, l = 0, r = k + 1;
    while (r < n) {
        bool ok = true;
        for (int i = l + 1; i < r; i++) if (days[i] < days[l] || days[i] < days[r]) { l = i; r = i + k + 1; ok = false; break; }
        if (ok) { best = min(best, max(days[l], days[r])); l = r; r = l + k + 1; }
    }
    return best == INT_MAX ? -1 : best;
}

Explanation

The problem is easier if we flip how we look at the data. Instead of "on day d, position bulbs[d] bloomed," we build days[pos] = the day that position bloomed. Now the question becomes a question about positions, which we can attack with a sliding window.

We want two bloomed bulbs with exactly k empty (still-dark) slots strictly between them. In position space that is a window whose two endpoints l and r are k + 1 apart, where the endpoints bloom earlier than every position in between.

For each candidate window we scan the inner positions l+1 .. r-1. If some inner position i blooms earlier than an endpoint (days[i] < days[l] or days[i] < days[r]), this window fails — and cleverly, we restart the window at that i, since i is the new earliest left boundary worth trying. If no inner position breaks the rule, the window is valid and the day both endpoints are up is max(days[l], days[r]); we keep the smallest such day.

Example: bulbs = [1, 3, 2], k = 1. Inverting gives days = [1, 3, 2] for positions 1, 2, 3. The window over positions 1 and 3 has inner position 2 blooming on day 3, later than both endpoints (days 1 and 2), so it is valid; the answer is max(1, 2) = 2.

Each position is visited a constant number of times as the window slides, so the whole scan is linear after the inversion step.

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