Mali Kaka looks after a row of garden plots at a school. The list flowerbed describes the row. A 1 means the plot already has a flower. A 0 means the plot is empty.
Flowers need space. You can not plant in a plot if the plot on its left or on its right has a flower. This is true for the flowers you plant too.
Given flowerbed and a whole number n, return true if you can plant n new flowers in empty plots and keep this rule. Otherwise, return false.
Examples
Example 1:
Input: flowerbed = [1,0,0,0,0,0,1], n = 2
Output: true
Explanation: Plant in plots 2 and 4. Plot 2 is not next to the flower in plot 0. Plot 4 is not next to the flower in plot 6. Plots 2 and 4 are not next to each other.
Example 2:
Input: flowerbed = [0,1,0,0,0,1,0], n = 2
Output: false
Explanation: Plots 0, 2, 4 and 6 are all next to a flower. Only plot 3 is free, so you can plant just 1 flower.
Example 3:
Input: flowerbed = [0,0,0,0], n = 2
Output: true
Explanation: Plant in plots 0 and 2. Plots 0 and 3 would work as well.