Is K Empty Slots easy or hard?

K Empty Slots is classified as a hard problem because it requires transforming the problem into bloom days and applying a non-obvious sliding window technique. Many initial solutions are O(n^2) or O(nk) before discovering the linear-time approach.

K Empty Slots Python/Java solution

Python and Java implementations usually follow either the O(n) sliding window method or an O(n log n) Binary Indexed Tree approach. The sliding window version is shorter and preferred in interviews, while the Fenwick Tree version highlights range query data structure knowledge.

How to solve K Empty Slots in O(n)?

First convert the input into a days array where days[i] represents the day the flower at position i blooms. Use two pointers representing a window of size k + 2. If any flower inside the window blooms earlier than the boundaries, shift the window; otherwise record the candidate day.

What is the best approach for K Empty Slots?

The optimal approach uses a sliding window over a precomputed bloom-day array and runs in O(n) time with O(n) space. Each window checks whether all flowers inside bloom later than the two boundary flowers. If the condition holds, the later boundary bloom day gives the answer.

Is K Empty Slots asked at Google/Amazon/Meta?

K Empty Slots is a known hard interview problem and has appeared in interviews at companies like Google and Amazon. It tests understanding of sliding window techniques, ordered structures, and interval validation logic.

What data structure is used in K Empty Slots?

Common solutions use arrays with a sliding window, Binary Indexed Tree (Fenwick Tree), Segment Tree, or ordered sets. These structures help track which flowers have bloomed and quickly check whether the gap between two flowers is empty.

What is the time complexity of K Empty Slots?

The best known solution runs in O(n) time using a sliding window over bloom days. A Binary Indexed Tree or Segment Tree solution runs in O(n log n) because each bloom requires a logarithmic update and query.

Description Solution Video 19:41

683. K Empty Slots

Hard38.0% acceptance1 companyPremium elsewhere, free here

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.length
1 <= n <= 2 * 10⁴
1 <= bulbs[i] <= n
bulbs is a permutation of numbers from 1 to n.
0 <= k <= 2 * 10⁴

Asked at 1 company

Google

Topics

Array Binary Indexed Tree Heap (Priority Queue)Monotonic Queue Ordered Set Queue Segment Tree Sliding Window

19:41

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,3,2]
1

Input

[1,2,3]
1

Your code is saved on this device.Solution