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.
We can use a Binary Indexed Tree to maintain the prefix sum of the bulbs. Every time we turn on a bulb, we update the corresponding position in the Binary Indexed Tree. Then we check if the k bulbs to the left or right of the current bulb are all turned off and the (k+1)-th bulb is already turned on. If either of these conditions is met, we return the current day.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the number of bulbs.
Python
Java
C++
Go
TypeScript
| 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 |
花花酱 LeetCode 683. K Empty Slots - 刷题找工作 EP76 • Hua Hua • 9,406 views views
Watch 9 more video solutions →Practice K Empty Slots with our built-in code editor and test cases.
Practice on FleetCode