683. K Empty Slots

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and 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].

Solution

(1) Java

(2) Python

class Solution:
    def kEmptySlots(self, flowers, k):
        """
        :type flowers: List[int]
        :type k: int
        :rtype: int
        """
        if not flowers or k < 0:
            return -1
        length = len(flowers)+1
        days = [0]*length
        for i, v in enumerate(flowers):
            days[v] = i+1
        #print(days)
        rst = length+1
        for i in range(1, length):
            v = days[i]
            #print("i={0},v={1}".format(i,v))
            left = i-k-1
            if left >= 1 and days[left] < v:
                failed = False
                for j in range(left+1, i):
                    if days[j] < v:
                        failed = True
                        break;
                if failed == False:
                    rst = min(rst, v)
            right = i+k+1
            if right < length and days[right] < v:
                failed = False
                for j in range(i+1, right):
                    if days[j] < v:
                        failed = True
                        break;
                if failed == False:
                    rst = min(rst, v)
        return -1 if rst == length+1 else rst

(3) Scala