683. k Empty Slots

683. k Empty Slots (1st TreeSet).java

// store all the flower position to a TreeSet, each time a flower bloom, we check the distance of this flower to 
// two closest flower is k or not, return the first data that satisfy the condition.
// TreeSet: Time = O(NlogN) Space = O(N)
 public int kEmptySlots(int[] flowers, int k) {
    if (flowers == null || k > flowers.length - 2) return -1;
    int N = flowers.length;
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i < N; i++) {
        set.add(flowers[i]); // include right and exclude left
        Integer lower = set.lower(flowers[i]);
        Integer higher = set.higher(flowers[i]);
        if (lower != null && flowers[i] - lower - 1 == k) return i + 1;
        if (higher != null && higher - flowers[i] - 1 == k) return i + 1;
    }
    return -1;
}

683. k Empty Slots (2nd Array).java

 /**
 * we store all flowers's blooming days in a array according to flowers' position. So when we traverse the array, we could see what day 
 * this flower will bloom. If there exist two flowers, there are k flowers between them and all the flowers have larger blooming date than 
 * these two flowers, then we could return the large date of this two flowers. Go through all the possible dates and find the earliest date
 * that satisfy this condition. Time = O(N), Space = O(N)
 */

public static int kEmptySlot(int[] flowers, int k){
	if (flowers == null || k > flowers.length - 2) return -1;
	int N = flowers.length;
	int[] days = new int[N + 1];
	for (int i = 0; i < N; i++) days[flowers[i]] = i + 1;
	int left = 1; int right = left + k + 1;
	int result = Integer.MAX_VALUE;
	while (right < N + 1) {
		int mid = left + 1; 
		while (mid < right) {
			if (days[mid] < days[left] || days[mid] < days[right]) break;
			mid++;		
		}
		if (mid == right) result = Math.min(result, Math.max(days[left], days[right]));
		left++;
		right = left + k + 1;
	}
	return result == Integer.MAX_VALUE ? -1 : result;
}

683. k Empty Slots (3rd TreeMap).java

// Not recommend in this exercise, but worth study how to deal with interval 
// k == 0 should be consider
//  Time = O(NlogN) Space = O(N)
public int kEmptySlots(int[] flowers, int k) {
    if (flowers == null || k > flowers.length - 2) return -1;
    int N = flowers.length;
    TreeMap<Integer, Integer> treeMap = new TreeMap<>();
    treeMap.put(1, N + 1); // include right and exclude left
    for (int i = 0; i < N; i++) {
        Map.Entry<Integer, Integer> entry = treeMap.floorEntry(flowers[i]);
        int left = entry.getKey(); int right = entry.getValue();
        if (left == flowers[i]) {
            if (k == 0 && left != 1) {
                return i + 1;
            }
            treeMap.remove(left);
            if (left + 1 < right) {
                if (right - left - 1 == k && right != N + 1) {
                    return i + 1;
                }
                treeMap.put(left + 1, right);
            }
        } else {
            if (left != 1 && flowers[i] - left == k) {
                return i + 1;
            }
            treeMap.put(left, flowers[i]);
            if (flowers[i] + 1 < right) {	
                if (right != N + 1 && right - flowers[i] - 1 == k) {
                    return i + 1;
                }
                treeMap.put(flowers[i] + 1, right);
            } else if (k == 0 && flowers[i] != N) {
                return i + 1;
            }
        }
    }
    return -1;
}