Can Place Flowers

Problem

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0’s and 1’s, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

Constraints

• 1 <= flowerbed.length <= 2 * 104
• flowerbed[i] is 0 or 1.
• There are no two adjacent flowers in flowerbed.
• 0 <= n <= flowerbed.length

Solution

The problem Can Place Flowers can be solved by finding earliest flowerbeds in which a new flower can be planted. In these cases, we can assume that a new flower is planted and move the index one more step instead of modifying the given array. Also, to make the comparison simpler, we can add empty flowerbeds before the beginning and after the end of the array.

Implementation

class Solution
{
  public:
    bool canPlaceFlowers(vector<int> &flowerbed, int n)
    {
        flowerbed.insert(flowerbed.begin(), 0);
        flowerbed.push_back(0);

        for (int i = 1; i < flowerbed.size() - 1; i++)
            if (flowerbed[i - 1] + flowerbed[i] + flowerbed[i + 1] == 0)
            {
                n -= 1;
                i += 1;
            }

        return n <= 0;
    }
};