Approach #1: Insert Into Sorted Structure [Accepted]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public int kEmptySlots(int[] flowers, int k) {
TreeSet<Integer> treeSet = new TreeSet();
int day = 0;
for (int flower: flowers) {
day++;
treeSet.add(flower);
Integer lower = treeSet.lower(flower)
Integer higher = treeSet.higher(flower);
if (lower != null && flower - lower - 1 == k ||
higher != null && higher - flower - 1 == k)
return day;
}
return -1;
}
}
link
Sliding Window
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26// Time Complexity: O(n)
class Solution {
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;
}
}