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


  • 57

    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;
    }


  • 6

    @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!

  • 0
    P

    Very smart solution! I like how you scan through from left to right. If we keep a window and update the minimum value, we have to keep track of all the values, which is much slower.


  • 8
    Y

    A really instructive sliding window solution. Just change several lines to make it more readable.

    public int kEmptySlots(int[] flowers, int k) {
        int[] days = new int[flowers.length];
        for (int i = 0; i < days.length; i++) {
            days[flowers[i] - 1] = i + 1;
        }
        int left = 0;
        int right = k + 1;
        int res = Integer.MAX_VALUE;
        for (int i = 1; right < days.length; i++) {
            // current days[i] is valid, continue scanning
            if (days[i] > days[left] && days[i] > days[right]) {
                continue;
            }
           // reach boundary of sliding window, since previous number are all valid, record result  
            if (i == right) {
                res = Math.min(res, Math.max(days[left],days[right]));
            }
            // not valid, move the sliding window
            left = i;
            right = left + k + 1;
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

  • 0
    J

    Can you explain why it is O(n), not O (n^2)


  • 0

    @Jinius It's straightforward....


  • 0
    E

    @yupengz1 Nice! Really helpful for me to understand!


  • 0
    E

    @Jinius Because it only used one layer for loop, but twice: first time, it load data into days[] and then in the second loop, it uses a sliding window to scan the array. You think it is O(n^2) because you might think that it scans all elements inside the window whenever the window move, but it does not.


Log in to reply
 

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