683. K Empty Slots

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 everyday 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, find out 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

 

Note:

  1. 1 <= N <= 20000
  2. 1 <= bulbs[i] <= N
  3. bulbs is a permutation of numbers from 1 to N.
  4. 0 <= K <= 20000

Rust Solution

struct Solution;

use std::collections::BTreeSet;

impl Solution {
    fn k_empty_slots(bulbs: Vec<i32>, k: i32) -> i32 {
        let n = bulbs.len();
        let mut set: BTreeSet<i32> = BTreeSet::new();
        for i in 0..n {
            let day = (i + 1) as i32;
            let mid = bulbs[i];
            if let Some(left) = set.range(..mid).next_back() {
                if mid - left - 1 == k {
                    return day;
                }
            }
            if let Some(right) = set.range(mid..).next() {
                if right - mid - 1 == k {
                    return day;
                }
            }
            set.insert(mid);
        }
        -1
    }
}

#[test]
fn test() {
    let bulbs = vec![1, 3, 2];
    let k = 1;
    let res = 2;
    assert_eq!(Solution::k_empty_slots(bulbs, k), res);
    let bulbs = vec![1, 3, 2];
    let k = 1;
    let res = 2;
    assert_eq!(Solution::k_empty_slots(bulbs, k), res);
}

Having problems with this solution? Click here to submit an issue on github.