Java Solution, Easy to understand, Set and BinarySearch


  • 0
    A
    class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        // algortithm 2017/09/24: maintain a list of interval; each blooming flower would in a new interval
        // so we need to find which one has "k" range
        // example: 1 6 3 4 2 5
        // checkPoints: 1 6, intervalRanges: 4
        // checkPoints: 1 3 6, intervalRanges: 4, 1, 2
        // checkPoints: 1 3 4 6, intervalRanges: 4, 1, 2, 0, 1
        if (null == flowers || 2 >= flowers.length || k > flowers.length-2) {
            return -1;
        }
        
        // a set recording all possible interval ranges as more flowers are blooming
        Set<Integer> intervalRanges = new HashSet<>();        
        List<Integer> checkPoints   = new ArrayList<>();
        
        // first two flowers
        checkPoints.add(Math.min(flowers[0], flowers[1]));
        checkPoints.add(Math.max(flowers[0], flowers[1]));
        intervalRanges.add(checkPoints.get(1) - checkPoints.get(0) - 1);
        
        for (int index = 2; index < flowers.length; index++) {
            // any intervals meeting condition?
            if (intervalRanges.contains(k)) {
                return index;   // the previous day meet the condition, but day is 1-based, so return index
            }
            
            // a new checkpoint to be added
            int newPoint  = flowers[index];
            int insertPos = Collections.binarySearch(checkPoints, newPoint);
            insertPos     = -(insertPos+1);
            checkPoints.add(insertPos, newPoint);
            
            // and this insertion results in new interval ranges
            int countCheckPoints = checkPoints.size();
            if (insertPos > 0 && insertPos < countCheckPoints - 1) {
                int previousPoint = checkPoints.get(insertPos - 1);
                int nextPoint     = checkPoints.get(insertPos + 1);
                intervalRanges.add(newPoint - previousPoint - 1);
                intervalRanges.add(nextPoint - newPoint - 1);
            } else if (0 == insertPos) {
                int nextPoint     = checkPoints.get(insertPos + 1);
                intervalRanges.add(nextPoint - newPoint - 1);
            } else {
                // last one
                int previousPoint = checkPoints.get(insertPos - 1);
                intervalRanges.add(newPoint - previousPoint - 1);
            }
            
        }
                        
        return -1;
    }
    

    }


Log in to reply
 

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