Watch 10 video solutions for K Empty Slots, a hard level problem involving Array, Binary Indexed Tree, Segment Tree. This walkthrough by Hua Hua has 9,406 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have n bulbs in a row numbered from 1 to n. Initially, all the bulbs are turned off. We turn on exactly one bulb every day until all bulbs are on after n days.
You are given an array bulbs of length n where bulbs[i] = x means that on the (i+1)th day, we will turn on the bulb at position x where i is 0-indexed and x is 1-indexed.
Given an integer k, return the minimum day number such that there exists two turned on bulbs that have exactly k bulbs between them that are all turned off. If there isn't such day, return -1.
Example 1:
Input: bulbs = [1,3,2], k = 1 Output: 2 Explanation: On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0] On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1] On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1] We return 2 because on the second day, there were two on bulbs with one off bulb between them.
Example 2:
Input: bulbs = [1,2,3], k = 1 Output: -1
Constraints:
n == bulbs.length1 <= n <= 2 * 1041 <= bulbs[i] <= nbulbs is a permutation of numbers from 1 to n.0 <= k <= 2 * 104Problem Overview: You receive an array bulbs where bulbs[i] tells which position blooms on day i + 1. The goal is to find the earliest day when two blooming flowers have exactly k unbloomed slots between them.
Approach 1: Brute Force Simulation (O(n * k) time, O(n) space)
Track which flowers have bloomed using a boolean array. After each day, check the newly bloomed position and look left and right to see if another bloomed flower exists exactly k + 1 distance away. Then verify the k slots between them remain unbloomed. This method directly simulates the condition but repeatedly scans segments of size k, making it inefficient for large inputs.
Approach 2: Binary Indexed Tree / Fenwick Tree (O(n log n) time, O(n) space)
Maintain a Fenwick Tree to track how many flowers have bloomed up to a given index. When a flower blooms at position p, query whether a flower exists at p - k - 1 or p + k + 1. Then use the Fenwick Tree to count how many flowers exist inside the interval between them. If the count inside the gap is zero, the condition is satisfied. Each update and range query runs in O(log n). This approach is reliable when you need fast prefix counts over dynamically updated positions, which is exactly what Binary Indexed Tree structures handle well.
Approach 3: Sliding Window with Bloom Days (O(n) time, O(n) space)
Create an array days where days[i] represents the day flower i blooms. Use a window of size k + 2 with two pointers representing the potential boundary flowers. For a valid window, every flower between them must bloom later than both boundaries. If an interior flower blooms earlier, the window shifts starting from that position. This method works because the earliest boundary bloom day determines when the condition is satisfied. It uses a technique similar to Sliding Window and can be optimized using ideas related to a Monotonic Queue.
Recommended for interviews: The sliding window approach is the expected optimal solution because it achieves O(n) time by preprocessing bloom days and scanning once. The Binary Indexed Tree solution is also strong and demonstrates knowledge of advanced data structures for dynamic range queries. Showing the brute force idea first demonstrates understanding of the problem constraints before moving to the optimized strategy.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n * k) | O(n) | Useful for understanding the condition and verifying logic on small inputs |
| Binary Indexed Tree (Fenwick Tree) | O(n log n) | O(n) | When dynamic prefix counts or range queries are required |
| Sliding Window on Bloom Days | O(n) | O(n) | Optimal solution for interviews and large inputs |