# 605 Can Place Flowers

Suppose 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 - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number **n**, return if **n** new flowers can be planted in it without violating the no-adjacent-flowers rule.

**Example 1:**

```
Input:
 flowerbed = [1,0,0,0,1], n = 1

Output:
 True
```

**Example 2:**

```
Input:
 flowerbed = [1,0,0,0,1], n = 2

Output:
 False
```

**Note:**

1. The input array won't violate no-adjacent-flowers rule.
2. The input array size is in the range of \[1, 20000].
3. **n** is a non-negative integer which won't exceed the input array size.

**The Idea:** To simplify things later, consider the edges of the array. If there are at least two zeros, this is it always optimal to place a flower on the absolution edge of array because this edge is not constrained by adjacent flowers in any way. Now having this done, we can simply iterate through the array, and count the consecutive zeros. We notice the following pattern with given `n` consecutive 0s. This is simply `math.floor((consec_count - 1) / 2`.

```
n | opt
-------
1 | 0
2 | 0
3 | 1
4 | 1
5 | 2
6 | 2
7 | 3
. | .
. | .
. | .
```

**Complexity:** O(N) time and O(1) space

```python
class Solution:
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """
        if len(flowerbed) is 1 and \
            flowerbed[0] is 0:
            return True
        if len(flowerbed) >= 2 and \
           flowerbed[0] is 0 and \
           flowerbed[1] is 0:
            flowerbed[0] = 1
            n -= 1

        if len(flowerbed) >= 3 and \
           flowerbed[-1] is 0 and \
           flowerbed[-2] is 0:
            flowerbed[-1] = 1
            n -= 1

        consec_count = 1
        for i in range(1, len(flowerbed)):
            if flowerbed[i-1] is flowerbed[i]:
                consec_count += 1
            else:
                n -= math.floor((consec_count - 1) / 2)
                consec_count = 1

        return n <= 0
```

**Testing**

```python
obj = Solution()
print(obj.canPlaceFlowers([1, 0, 0, 0, 1], 1))  # T
print(obj.canPlaceFlowers([1, 0, 0, 0, 1], 2))  # F
print(obj.canPlaceFlowers([1, 0, 0, 1, 0, 1], 1))  # F
print(obj.canPlaceFlowers([0, 0, 1, 0, 1, 1], 1))  # T
print(obj.canPlaceFlowers([0, 0, 0, 0, 0, 0], 3))  # T
print(obj.canPlaceFlowers([0, 0, 0, 0, 0, 0], 4))  # F
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/605-can-place-flowers.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.