My C++ solution with O(n) TC and O(1) SC and less comparation for every plot checking.


  • 0
    M

    class Solution {
    public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n)
    {
    if (n <= 0 ) return true;
    size_t size = flowerbed.size();
    if( size < 1 || size < 2*n-1) return false;
    int freeCount = 0;
    size_t index = 0;

        if(flowerbed[0] == 0)
        {
            if(size == 1 || flowerbed[1] == 0) --n;//plant one for the first plot if empty            
        }        
        ++index;
        
        if(size > 2 && flowerbed[size-1] == 0 && flowerbed[size-2] == 0) --n;//plant one for last plot if empty
        
        while(index < size-1 && n > 0) //range in 1 ~ size-1
        {
            freeCount = 0;
            while(index < size-1 && flowerbed[index] == 1) ++index;
            while(index < size-1 && flowerbed[index++] == 0) ++freeCount;
            n -= (freeCount-1)/2;
        }
        
        return (n <= 0);
            
    }
    

    };


Log in to reply
 

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