402 ms C++ solution using unordered_map


  • 0
    S
    class Solution {
    public:
        int max(int a, int b)
        {
            return a>b?a:b;
        }
        int min(int a, int b)
        {
            return a<b?a:b;
        }
        int kEmptySlots(vector<int>& flowers, int k) {
            int n = flowers.size();
            if( n <= k)
                return -1;
            unordered_map<int, int>m;
            int dday = INT_MAX;
            for(int i=0;i<n;++i)
                m[flowers[i]] = i;
            for(auto i=m.begin(); i!=m.end(); ++i)
            {
                int pos = i->first;
                int day = i->second;
                if(m.find(pos+k+1) != m.end()){
                    int day2 = m[pos+k+1];
                    int pos2 = pos+k+1;
                    bool f = false;
                    // make sure all flowers in between arent blooming
                    for(int j=min(pos, pos2)+1;j<max(pos, pos2);j++){
                        if(m[j] < max(day, day2))
                        {
                            f = true;
                            break;
                        }
                    }
                    
                    if(!f)
                    {
                        dday = min(dday, max(day, day2)+1);
                    }
                }
            }
            return dday==INT_MAX?-1:dday;
        }
    };
    

    Steps:

    • Store the position as the key and the day as the value for each flower

    • Iterate through the map and get each position and the pos+k as the next position

    • For all positions between pos1 and pos2, check if they bloom before the max day

    • If any flower does, immediately break out and try the next position

    • Else store it in "dday" and calculate the minimum "dday"

    • Return minimum "dday" or INT_MAX if no such day exists


Log in to reply
 

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