leetcode683

Posted on | In

683. K Empty Slots

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn’t such day, output -1.

Example 1:
Input:
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.
Example 2:
Input:
flowers: [1,2,3]
k: 1
Output: -1
Note:
The given array will be in the range [1, 20000].

Idea

Through treeset, we may find the ceiling and floor of the new pos, and we can check whether the new pos is k slots away from its ceiling or floor. If so, it’s the answer.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < flowers.length; i++) {
            int pos = flowers[i];
            Integer left = set.floor(pos - 1);
            Integer right = set.ceiling(pos + 1);
            if (left != null && left == pos - k - 1) {
                return i + 1;
            }
            if (right != null && pos == right - k - 1) {
                return i + 1;
            }
            set.add(pos);
        }
        return -1;
    }
}

Java

The ceiling(E e) method is used to return the least element in this set greater than or equal to the given element, or null if there is no such element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package com.tutorialspoint;

import java.util.Iterator;
import java.util.TreeSet;

public class TreeSetDemo {
   public static void main(String[] args) {

      // creating a TreeSet 
      TreeSet <Integer>treeadd = new TreeSet<Integer>();

      // adding in the tree set
      treeadd.add(12);
      treeadd.add(11);
      treeadd.add(16);
      treeadd.add(15);

      // getting ceiling value for 13
      System.out.println("Ceiling value for 13: "+treeadd.ceiling(13));   
   }     
}
# print: Ceiling value for 13: 15

The floor(E e) method is used to return the greatest element in this set less than or equal to the given element, or null if there is no such element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package com.tutorialspoint;

import java.util.TreeSet;

public class TreeSetDemo {
   public static void main(String[] args) {

      // creating a TreeSet 
      TreeSet <Integer>treeadd = new TreeSet<Integer>();

      // adding in the tree set
      treeadd.add(12);
      treeadd.add(11);
      treeadd.add(16);
      treeadd.add(15);

      // getting the floor value for 13
      System.out.println("Floor value for 13: "+treeadd.floor(13));   
   }    
} 
# print: Floor value for 13: 12