[Java/C++] Simple O(n) solution


  • 43

    It seems that this question has some mistakes. I think there are two places that might lead to misunderstandings: (please feel free to tell me if I'm incorrect)

    1. flowers[i] = x should mean that the unique flower that blooms at day i+1 (not i) will be at position x.
    2. If you can get multiple possible results, then you need to return the minimum one.

    The idea is to use an array days[] to record each position's flower's blooming day. That means days[i] is the blooming day of the flower in position i+1. We just need to find a subarray days[left, left+1,..., left+k-1, right] which satisfies: for any i = left+1,..., left+k-1, we can have days[left] < days[i] && days[right] < days[i]. Then, the result is max(days[left], days[right]).

    Java version:

    public int kEmptySlots(int[] flowers, int k) {
            int[] days =  new int[flowers.length];
            for(int i=0; i<flowers.length; i++)days[flowers[i] - 1] = i + 1;
            int left = 0, right = k + 1, res = Integer.MAX_VALUE;
            for(int i = 0; right < days.length; i++){
                if(days[i] < days[left] || days[i] <= days[right]){
                    if(i == right)res = Math.min(res, Math.max(days[left], days[right]));   //we get a valid subarray
                    left = i; 
                    right = k + 1 + i;
                }
            }
            return (res == Integer.MAX_VALUE)?-1:res;
        }
    

    C++ version:

    int kEmptySlots(vector<int>& flowers, int k) {
            vector<int> days(flowers.size());
            for(int i=0; i<flowers.size();i++)days[flowers[i] - 1] = i + 1;
            int left = 0, right = k + 1, res = INT_MAX;
            for(int i = 0; right < days.size(); i++){
                if(days[i] < days[left] || days[i] <= days[right]){   
                    if(i == right)res = min(res, max(days[left], days[right]));    //we get a valid subarray
                    left = i, right = k + 1 + i;
                }
            }
            return (res == INT_MAX)?-1:res;
        }
    
    

  • 1

    Hope your advice!


  • 0
    S

    The last scanning step is awesome!


  • 0

    impressive. I was also trying to slide window but did not figure out how to update border


  • 1
    L

    Why does it have to be the minimum result? It doesn't say in the question that the first correct day should be returned. This should be updated in the question


  • 0
    H

    @Vincent-Cai
    nice solution! but a little hard to understand :)
    at :
    if(days[i] < days[left] || days[i] <= days[right]){
    if(i == right)res = min(res, max(days[left], days[right])); //we get a valid subarray
    left = i, right = k + 1 + i;
    }


  • 2

    @huajiaaaa There are two cases that we need to update left and right: 1. i arrives the position right (it means that we get a vliad subarray); 2. we find days[i] < days[left] || days[i] < days[right] (it means that the pre-assumed subarray is not correct).


  • 0
    H

    @Vincent-Cai Thank you very much! I have understood:)


  • 1
    J

    I really love the scanning process, where we set left = i when found invalid pre-subarray.
    It make use of the previous information scanned, and thanks to this idea, we can achieve O(n) time cost. Appreciate it.


  • 0
    B
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.