K Empty Slots

Problem#

bulbs[i] is the slot that turns on day i+1 (1-indexed slot, distinct). Return the first day on which there exist two on-slots exactly k slots apart with all slots between them off — or -1.

Examples#

bulbs = [1,3,2], k = 1 → 2
bulbs = [1,2,3], k = 1 → -1

Hints#

Hint 1

Invert: days[slot] = day it blooms. The answer is the first window [i, i+k+1] where max(days[i+1..i+k]) < min(days[i], days[i+k+1]).

Approach#

Build days[i] = day slot i blooms. Slide a window of length k + 2: it’s valid iff the two endpoint days are both less than every interior day. Equivalently, the smaller endpoint day is the answer when interior all exceed it.

Solution#

class Solution {
public:
    int kEmptySlots(vector<int>& bulbs, int k) {
        int n = bulbs.size();
        vector<int> days(n);
        for (int i = 0; i < n; ++i) days[bulbs[i] - 1] = i + 1;
        int ans = INT_MAX;
        int 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) {
                ans = min(ans, max(days[l], days[r]));
                l = r; r = r + k + 1;
            }
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

import "math"

func kEmptySlots(bulbs []int, k int) int {
    n := len(bulbs)
    days := make([]int, n)
    for i := 0; i < n; i++ {
        days[bulbs[i]-1] = i + 1
    }
    ans := math.MaxInt32
    l, r := 0, k+1
    for r < n {
        ok := true
        for 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 {
            cand := days[l]
            if days[r] > cand {
                cand = days[r]
            }
            if cand < ans {
                ans = cand
            }
            l = r
            r = r + k + 1
        }
    }
    if ans == math.MaxInt32 {
        return -1
    }
    return ans
}

from typing import List

class Solution:
    def kEmptySlots(self, bulbs: List[int], k: int) -> int:
        n = len(bulbs)
        days = [0] * n
        for i in range(n):
            days[bulbs[i] - 1] = i + 1
        ans = float('inf')
        l, r = 0, k + 1
        while r < n:
            ok = True
            i = l + 1
            while i < r:
                if days[i] < days[l] or days[i] < days[r]:
                    l = i
                    r = i + k + 1
                    ok = False
                    break
                i += 1
            if ok:
                cand = max(days[l], days[r])
                if cand < ans:
                    ans = cand
                l = r
                r = r + k + 1
        return -1 if ans == float('inf') else int(ans)

function kEmptySlots(bulbs, k) {
    const n = bulbs.length;
    const days = new Array(n).fill(0);
    for (let i = 0; i < n; i++) days[bulbs[i] - 1] = i + 1;
    let ans = Infinity;
    let 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) {
            const cand = Math.max(days[l], days[r]);
            if (cand < ans) ans = cand;
            l = r;
            r = r + k + 1;
        }
    }
    return ans === Infinity ? -1 : ans;
}

class Solution {
    public int kEmptySlots(int[] bulbs, int k) {
        int n = bulbs.length;
        int[] days = new int[n];
        for (int i = 0; i < n; i++) days[bulbs[i] - 1] = i + 1;
        int ans = Integer.MAX_VALUE;
        int 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) {
                ans = Math.min(ans, Math.max(days[l], days[r]));
                l = r;
                r = r + k + 1;
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

function kEmptySlots(bulbs: number[], k: number): number {
    const n = bulbs.length;
    const days: number[] = new Array(n).fill(0);
    for (let i = 0; i < n; i++) days[bulbs[i] - 1] = i + 1;
    let ans = Infinity;
    let 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) {
            const cand = Math.max(days[l], days[r]);
            if (cand < ans) ans = cand;
            l = r;
            r = r + k + 1;
        }
    }
    return ans === Infinity ? -1 : ans;
}

Editorial#

The inversion slot → day is the key trick. With the inversion, the “k empty between two on” condition is a simple range-min vs endpoint comparison. The sliding-with-skip pattern (advance l to the first interior violation) keeps the algorithm linear amortized: each index is examined O(1) times.

Complexity#

Time: O(n) amortized.
Space: O(n).

Problem#

Examples#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#