683 K Empty Slots

683. K Empty Slots

1. Question

There is a garden withNslots. In each slot, there is a flower. TheNflowers will bloom one by one inNdays. In each day, there will beexactlyone flower blooming and it will be in the status of blooming since then.

Given an arrayflowersconsists of number from1toN. Each number in the array represents the place where the flower will open in that day.

For example,flowers[i] = xmeans that the unique flower that blooms at dayiwill be at positionx, whereiandxwill be in the range from1toN.

Also given an integerk, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them iskand these flowers are not blooming.

If there isn't such day, output -1.

Example 1:

Input:

flowers: [1,3,2] k: 1

Output: 2

Explanation: In the second day, the first and the third flower have become blooming.

Example 2:

Input:

flowers: [1,2,3] k: 1

Output: -1

Note:

1. The given array will be in the range [1, 20000].

2. Implementation

(1) Brute Force

对于每个flowers[i]，我们都分别检查在它之前的k个位置，在它的之后的k个位置是否有花，如果有的话，它们之间的是否有k个empty slot，如果有的话，就返回天数。注意这里天数是从1开始算的，而数组是以0开始，所以返回i + 1

class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        if (flowers == null || k >= flowers.length) {
            return -1;
        }

        int n = flowers.length;
        int[] slots = new int[n + 1];

        for (int i = 0; i < n; i++) {
            if (isValid(flowers[i], k, n, slots)) {
                return i + 1;
            }
        }
        return -1;
    }

    public boolean isValid(int curSlot, int k, int n, int[] slots) {
        slots[curSlot] = 1;

        if (curSlot + k + 1 <= n && slots[curSlot + k + 1] == 1) {
            for (int i = 1; i <= k; i++) {
                if (slots[curSlot + i] == 1) {
                    return false;
                }
            }
            return true;
        }

        if (curSlot - k - 1 >= 0 && slots[curSlot - k - 1] == 1) {
            for (int i = 1; i <= k; i++) {
                if (slots[curSlot - i] == 1) {
                    return false;
                }
            }
            return true;
        }

        return false;
    }
}

(2) Binary Search Tree

利用Binary Search Tree的性质，可以找出一个flowers[i]前一个的key和后一个key，如果刚好之间间隔k，则返回天数。这里我们用treeSet来实现binary search tree

class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        if (flowers == null || k >= flowers.length) {
            return -1;
        }

        TreeSet<Integer> tree = new TreeSet();
        int day = 0;

        for (int flower : flowers) {
            ++day;
            tree.add(flower);

            Integer low = tree.lower(flower);
            Integer high = tree.higher(flower);

            if ((low != null && low == flower - k - 1) 
                || (high != null && high == flower + k + 1)) {
                return day;
            }
        }
        return -1;
    }
}

3. Time & Space Complexity

Brute Force: 时间复杂度O(nk), n是flowers数组的size，在这到题指的是天数，空间复杂度O(n)

Binary Search Tree: 时间复杂度O(nlogn), 空间复杂度O(n)