# 605\_Can Place Flowers

## 605. Can Place Flowers

Level: easy

Tag: array

## Question

```
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
```

### Idea

**Important trick: add 0 at the beginning and in the end of flowerbed. This action won't change if the first and last plot can plant flower.**

Scan every plot in the original flowerbed, if it's empty, the plot on the left is empty and the plot on the right is also empty, then this plot can plant flower.

Count how many plots can plant flowers, and compare with `n`.

.

### Complexity

* Time:$$O(n)$$ 
* Space:$$O(1)$$

### Solution

```python
class Solution(object):
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """

        count = 0

        # important: add 0 at the begining and in the end
        # won't change if the first and last plot can plant flower
        flowerbed = [0] + flowerbed + [0]

        # scan each plot, check if it can plant flower
        for i in range(1, len(flowerbed)-1):
            if flowerbed[i-1:i+2] == [0,0,0]:
                count += 1
                flowerbed[i] = 1
            if count >= n:
                return True    

        return False
```


---

# 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://lei-d.gitbook.io/leetcode/array/605can-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.