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

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

``````

• The last scanning step is awesome!

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

• 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

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

• @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).

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

• 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.

• This post is deleted!

• 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.

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

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

• @Jinius It's straightforward....

• @yupengz1 Nice! Really helpful for me to understand!

• @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.

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