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 <= N <= 20000
1 <= bulbs[i] <= N
bulbs is a permutation of numbers from 1 to N.
0 <= K <= 20000

Solution

  1. TreeMap
  2. Sliding Window use day[i] represents the day that bulb i+1 is turned on for i belonging to left + 1, left + 2, ... , left + k, it satisfies day[i] > day[left] && day[i] > day[right] ## Complexity
  3. O(NlogN) the insertion of TreeMap cost O(logN) O(N)
  4. O(N) O(1) ## Code java class Solution { public int kEmptySlots(int[] bulbs, int K) { TreeSet<Integer> active = new TreeSet<>(); for(int i=0; i<bulbs.length; i++){ active.add(bulbs[i]); Integer lower = active.lower(bulbs[i]); if(lower != null && bulbs[i] - lower == K+1) return i+1; Integer higher = active.higher(bulbs[i]); if(higher != null && higher - bulbs[i] == K+1) return i+1; } return -1; } }
class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        
        int res = Integer.MAX_VALUE;
        int[] day = new int[flowers.length + 1];
        for (int i = 0; i < flowers.length; i ++) {
            // day[i] is the day when the flower at position i blooms
            // day[0] is useless here
            day[flowers[i]] = i+1;
        }
        
        // we now are supposed to find a subarray of day[left, right] where its length is k+2 
        // and all i that left < i < right, we have day[i] > day[left] and day[i] > day[right]
        int left = 1, right = k + 2;
        for (int i = 2; right < day.length; i++) {
            if (i == right) {
                // found a sub array
                res = Math.min(res, Math.max(day[left], day[right]));
                left = i;
                right = left + k + 1;
            } else if (day[i] < day[left] || day[i] < day[right]) {
                left = i;
                right = left + k + 1;
            }
        }
        
        return (res == Integer.MAX_VALUE)?-1:res;
    }

}