Two points , O(n) time, O(n) space solution


  • 0
    T

    setup bloom time for each flower, dp[i] = n means for flower index of i is bloom at nth day.
    setup high = low + k +1;
    when dp[high] and dp[low] is the lowest two values index from low to high. means low to high is a valid answer.

    for i (low < i < high) , if dp[i] < dp[low] OR dp[i] < dp[high] , means low to high is not a valid answer,
    when dp[i] > dp[high] && dp[i] < dp[low] , means i is not a valid low index, so low = i+1, high = low+k+1
    when dp[i] < dp[high] , means i is possible a valid answer. . so set low = i, high = low+k +1

    public class Solution {
        public int KEmptySlots(int[] flowers, int k) {
            var len = flowers.Length;
            
            var dp = new int[len+1];
            
            for(int i = 0;i<len;i++){
                dp[flowers[i]] = i+1;
            }
            
            int low = 1;
            int high = low+k+1;
            int result = len+1;
            while(high <= len){
                bool valid = true; 
                for(int i = low+1;i<high;i++){
                    if(dp[i] < dp[low] || dp[i] < dp[high]){
                        if(dp[i] > dp[high]){
                            low = i+1;
                        }else{
                            low = i;
                        }
                        high = low+k+1;
                        valid = false;
                        break;
                    }
                }
                if(valid){
                    result = Math.Min(result,Math.Max(dp[low],dp[high]));
                    low = high;
                    high = low+k+1;
                }
            }
            return result > len ? -1 : result;
        }
    }
    

Log in to reply
 

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