Code Implementation

from bisect import insort, bisect_left

class Solution:
    def kEmptySlots(self, bulbs, k):
        active = []
        for day, bulb in enumerate(bulbs):
            pos = bulb
            idx = bisect_left(active, pos)
            # Check left neighbor
            if idx > 0 and pos - active[idx-1] == k+1:
                return day+1
            # Check right neighbor
            if idx < len(active) and active[idx] - pos == k+1:
                return day+1
            insort(active, pos)
        return -1
      

#include <set>
#include <vector>
using namespace std;

class Solution {
public:
    int kEmptySlots(vector<int>& bulbs, int k) {
        set<int> active;
        for (int day = 0; day < bulbs.size(); ++day) {
            int pos = bulbs[day];
            auto it = active.insert(pos).first;
            // Check left neighbor
            if (it != active.begin()) {
                auto left = prev(it);
                if (pos - *left == k + 1) return day + 1;
            }
            // Check right neighbor
            auto right = next(it);
            if (right != active.end()) {
                if (*right - pos == k + 1) return day + 1;
            }
        }
        return -1;
    }
};
      

import java.util.*;

class Solution {
    public int kEmptySlots(int[] bulbs, int k) {
        TreeSet<Integer> active = new TreeSet<>();
        for (int day = 0; day < bulbs.length; ++day) {
            int pos = bulbs[day];
            active.add(pos);
            Integer lower = active.lower(pos);
            Integer higher = active.higher(pos);
            if (lower != null && pos - lower == k + 1) return day + 1;
            if (higher != null && higher - pos == k + 1) return day + 1;
        }
        return -1;
    }
}
      

class Solution {
    kEmptySlots(bulbs, k) {
        let active = [];
        for (let day = 0; day < bulbs.length; ++day) {
            let pos = bulbs[day];
            // Binary search insert
            let left = 0, right = active.length;
            while (left < right) {
                let mid = (left + right) >> 1;
                if (active[mid] < pos) left = mid + 1;
                else right = mid;
            }
            // Check left neighbor
            if (left > 0 && pos - active[left-1] === k+1) return day + 1;
            // Check right neighbor
            if (left < active.length && active[left] - pos === k+1) return day + 1;
            active.splice(left, 0, pos);
        }
        return -1;
    }
}
      

Problem Description

You are given an array bulbs of length N, where bulbs[i] indicates the position (1-indexed) of the bulb that is turned on on day i + 1. All bulbs are initially off. Each day, exactly one bulb is turned on.

You are also given an integer k. Your task is to determine the earliest day (smallest index + 1) such that there exist two bulbs that are turned on, with exactly k bulbs between them that are still off. In other words, find the earliest day when there are two turned-on bulbs with exactly k consecutive bulbs between them, and all these bulbs are still off.

If such a day does not exist, return -1.

• Each bulb is turned on exactly once, and no bulb is turned on twice.
• You cannot reuse bulbs or days; each day is unique.
• Input constraints: 1 <= N <= 2 * 10^4, 1 <= bulbs[i] <= N, 0 <= k < N.

Thought Process

A naive approach would be, for each day, to check all pairs of bulbs that are on and see if there are exactly k bulbs between them that are still off. However, this would be very inefficient, especially for large arrays, since it would require checking all pairs for every day.

To optimize, we can shift our perspective: instead of focusing on the bulbs that are off, we can focus on the bulbs that are on, and maintain the order in which they are turned on. By keeping track of the positions of bulbs that are on, we can efficiently check, each time a new bulb is turned on, if it forms a valid pair with its immediate neighbors (left and right) in the sequence of turned-on bulbs.

This leads us to use a data structure that supports fast insertion and neighbor queries, such as a balanced binary search tree (BST), a TreeSet (Java), or a sorted array with binary search (Python's bisect). This way, for each new bulb, we can check only its immediate left and right neighbors for the k-gap condition, rather than every possible pair.

Solution Approach

• Step 1: Initialize an empty data structure (e.g., a BST, TreeSet, or sorted array) to keep track of the positions of bulbs that have been turned on.
• Step 2: Iterate through each day (and thus each element in bulbs), and for each bulb that is turned on:
  • Insert its position into the data structure, maintaining sorted order.
  • Find the immediate left and right neighbors of the current bulb in the set of turned-on bulbs.
  • If the distance between the current bulb and its left neighbor is exactly k + 1, then all bulbs in between must still be off (since they have not yet appeared in the data structure). The same logic applies to the right neighbor.
  • If such a neighbor exists, return the current day number (1-based).
• Step 3: If no such pair is found after processing all days, return -1.

The key insight is that by maintaining the set of turned-on bulbs in sorted order, and only checking adjacent bulbs, we can efficiently determine if the k-gap condition is satisfied. This approach avoids the need to check every possible pair, reducing the time complexity significantly.

Example Walkthrough

Let's work through an example with bulbs = [1, 3, 2] and k = 1.

• Day 1: Bulb at position 1 is turned on. The set of turned-on bulbs is {1}. No neighbors to check.
• Day 2: Bulb at position 3 is turned on. The set is now {1, 3}. For bulb 3, left neighbor is 1 (distance is 2, which is k + 1). So, bulbs between 1 and 3: position 2, which is still off. We've found a valid pair!
• Thus, the answer is 2 (the earliest day this occurs).

If we continued to day 3 (bulb at position 2), the set would be {1, 2, 3}, but there would no longer be any pair with exactly 1 off bulb between them.

Time and Space Complexity

• Brute-force approach: For each day, check all pairs of turned-on bulbs and see if the bulbs between them are off. This results in O(N^2) time complexity, which is too slow for large N.
• Optimized approach (BST or sorted array):
  • Each insertion and neighbor lookup in a BST or TreeSet takes O(log N) time.
  • We do this for each of the N bulbs, so total time complexity is O(N log N).
  • Space complexity is O(N), since we store up to N bulb positions.

This optimization is possible because we only ever need to check the immediate neighbors for each bulb turned on, rather than all possible pairs.

Summary

The "K Empty Slots" problem asks for the earliest day when two bulbs are on with exactly k off bulbs between them. The brute-force approach is inefficient, but by maintaining a sorted set of turned-on bulb positions and checking only immediate neighbors, we can solve the problem efficiently in O(N log N) time. This solution elegantly leverages the properties of sorted data structures and the problem's constraints to avoid unnecessary work.