K Empty Slots LeetCode

K Empty Slots is a very famous problem on LeetCode. The problem statement is like that- A garden is consists of n slots containing a flower each. All the flowers are unbloomed initially. Given an array a[ ] of flowers and an integer k. Considering i stating from 0, i+1’th flower will bloom on day a[i] . For example – let a [ ] = {1, 3, 2} means the first flower will bloom on day 1, the second flower will bloom on day 3 and the third flower will bloom on day 2. Print the day on which there will be k unbloomed flowers between two bloomed flowers else print -1 if no answer exists. For example – ln a [ ] = {1, 3, 2} and k=1, the output is 2 as on the second day first and the third flower will be bloomed with k i.e. 1 unbloomed flower between them.

Example

Input

a[ ] = {1, 4, 3, 2, 5}

k = 2

Output

2

Input 

a[ ] = {1, 2, 3, 4}

k = 1

Output

-1

Algorithm

Now we know the problem statement of K Empty Slots LeetCode. So, without taking much time we move to algorithm used to solve this problem.

1. Initialize an array a and an integer k.
2. Initialize another array days to store days o which each flower will bloom.
3. Traverse the days array with i starting from zero and update the array as days[a[i]] = i+1.
4. Set result as INT_MAX.
5. Traverse the array again. Store the left and right values with k slots between in 2 variables and find it’s maximum.
6. At each step traverse from 1 to k and check if days[i+j] is less than the maximum value break the inner loop and set flag false.
7. If the flag is true, set result as maximum value.
8. If the result is equal to INT_MAX return -1 else return res.

Implementation

C++ Program for K Empty Slots LeetCode

#include <bits/stdc++.h>
using namespace std;
int kSlots(int a[], int k, int n) {
    int days[n+1];
    for(int i=0; i<n; i++){
        days[a[i]] = i+1;
    }    
    int res = INT_MAX;    
    n = sizeof(days)/sizeof(days[0]);   
    for(int i=1; i<n; i++){
        int l = days[i];
        int r = days[i+k+1];
        int m1 = max(l, r);
        int m2 = min(l, r); 
        bool flag = true;
        for(int j=1; j<=k; j++){
            if(days[i + j]<m1){
                flag = false;
                break;
            }
        }
        if(flag && m1<res){
            res = m1;
        }
    }
    return res == INT_MAX ? -1 : res;
}
int main(){
  int a[] = {1, 3, 2}; 
  int k = 1;
  int n = sizeof(a)/sizeof(a[0]);
  cout<<kSlots(a, k, n);
  return 0;
}

2

Java Program for K Empty Slots LeetCode

class kEmptySlots{
    
    static int kSlots(int[] a, int k) {
        int[] days = new int[a.length + 1];
        
        for(int i=0; i<a.length; i++) {
            days[a[i]] = i+1;
        }
        
        int res = Integer.MAX_VALUE;
        
        for(int i=1; i< days.length-k-1; i++){
            int l = days[i];
            int r = days[i+k+1];
            
            int max = Math.max(l, r);
            int min = Math.min(l, r);
            
            boolean flag = true;
            for(int j=1; j<=k; j++){
                if(days[i + j]<max){
                    flag = false;
                    break;
                }
            }
        
            if(flag && max<res){
                res = max;
            }
        }
    
        return res == Integer.MAX_VALUE ? -1 : res;
    }
    
    public static void main (String[] args){
        int a[] = {1, 3, 2};
        int k = 1;
        System.out.println(kSlots(a, k));
    }
}

2

Complexity Analysis

Time Complexity: O(N*K) where N is the size of the given array, and K is the given value which denotes the number of unbloomed flowers between two bloomed flowers.

Space Complexity: O(N) where N is the size of the given array. Here we an array days[n] for storing the bloomed flower information.

References