K empty slots

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

38.0% acceptance

Mar 31, 2026

829

706

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn k_empty_slots(bulbs: Vec<i32>, k: i32) -> i32 {
    let n = bulbs.len();
    // days[pos] = day bulb at position pos is turned on (0-indexed position)
    let mut days = vec![0usize; n];
    for (day, &pos) in bulbs.iter().enumerate() {
      days[(pos - 1) as usize] = day + 1;
    }
    
    let k = k as usize;
    if n < k + 2 { return -1; }
    
    // Sliding window of size k+2: [left, left+k+1]
    // We need all days[left+1..=left+k] > max(days[left], days[left+k+1])
    let mut result = usize::MAX;
    let mut left = 0;
    let mut right = left + k + 1;
    let mut i = left + 1;
    
    while right < n {
      // Check if days[i] < days[left] || days[i] < days[right]
      if i < right {
        if days[i] < days[left] || days[i] < days[right] {
          // Invalid window, slide
          left = i;
          right = left + k + 1;
          i = left + 1;
        } else {
          i += 1;
        }
      } else {
        // Valid window found
        result = result.min(days[left].max(days[right]));
        left = right;
        right = left + k + 1;
        i = left + 1;
      }
    }
    
    if result == usize::MAX { -1 } else { result as i32 }
  }
}