Solution Explanation: K Empty Slots

This problem asks to find the minimum day when two turned-on bulbs have exactly k turned-off bulbs between them. A brute-force approach would be highly inefficient. The optimal solution leverages a Binary Indexed Tree (BIT) to efficiently track the state of the bulbs.

Binary Indexed Tree (BIT): A BIT is a data structure that allows for efficient prefix sum queries and updates in O(log n) time. In this context, we use a BIT to track the number of bulbs turned on up to a given position.

Algorithm:

1. Initialization: Create a BIT of size n (number of bulbs), initially all zeros, and a boolean array vis to track which bulbs are turned on.

2. Iteration: Iterate through the bulbs array. For each bulb x on day i:

   • Update the BIT to reflect that bulb x is now on.
   • Check for a pair of on bulbs separated by exactly k off bulbs:
     • Check to the left: If x - k - 1 > 0, check if bulb x - k - 1 is on (vis[x - k - 1] == true) and the number of bulbs turned on between x - k - 1 and x - 1 is zero. This is efficiently checked using BIT queries: tree.query(x - 1) - tree.query(x - k - 1) == 0.
     • Check to the right: Similarly, if x + k + 1 <= n, check if bulb x + k + 1 is on and the number of bulbs turned on between x and x + k is zero.
   • If either condition is true, return i (the current day).

3. No Solution: If the loop completes without finding a pair, return -1.

Time Complexity: O(n log n) - The dominant operation is updating and querying the BIT, which takes O(log n) time each. We perform these operations n times.

Space Complexity: O(n) - We use a BIT of size n and a boolean array vis of size n + 1.

Code Implementations (with explanations):

The code implementations in Python, Java, C++, Go, and TypeScript all follow the same algorithmic structure, differing only in syntax and data structure implementations. The BIT implementation is consistent across all languages.

Example (Python):

class BinaryIndexedTree:
    # ... (BIT implementation as shown before) ...
 
class Solution:
    def kEmptySlots(self, bulbs: List[int], k: int) -> int:
        n = len(bulbs)
        tree = BinaryIndexedTree(n)  # Initialize BIT
        vis = [False] * (n + 1)     # Track turned-on bulbs
 
        for i, x in enumerate(bulbs, 1):  # Iterate through bulbs (days)
            tree.update(x, 1)          # Turn on bulb x
            vis[x] = True
 
            # Check left and right for k empty slots
            y = x - k - 1
            if y > 0 and vis[y] and tree.query(x - 1) - tree.query(y) == 0:
                return i
            y = x + k + 1
            if y <= n and vis[y] and tree.query(y - 1) - tree.query(x) == 0:
                return i
        return -1  # No solution found
 

The other languages (Java, C++, Go, TypeScript) have very similar structures, differing mainly in their syntax and how the Binary Indexed Tree is implemented. The core logic remains the same. The BIT implementation details are provided in the previous response. Each example shows how the BIT is used to efficiently check the condition of having k empty slots between two lit bulbs.