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.
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
Constraints:
1 <= flowerbed.length <= 2 * 104flowerbed[i] is 0 or 1.flowerbed.0 <= n <= flowerbed.lengthThis approach involves a single pass through the flowerbed array, considering each plot one by one. For each zero found, we check whether it's possible to plant a flower by ensuring that both neighboring plots (if they exist) are not planted. If it's possible, we plant the flower (i.e., change the zero to one) and reduce the count of n. The process stops early if n becomes zero. This greedy method ensures efficiency by trying to plant a flower at each opportunity.
This C solution iterates through the flowerbed, checking the conditions for planting flowers by ensuring adjacent plots are empty. It directly modifies the flowerbed array in the process, which simulates planting the flowers. If the required number of flowers (n) is planted, it returns early.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m), where m is the length of the flowerbed array.
Space Complexity: O(1), as no extra space is used except for variables.
This approach calculates the maximum number of flowers that can be planted by counting the stretches of zeros between planted flowers or array boundaries. For each encounter of a continuous stretch of zeros, determine how many flowers can be planted and accumulate this count until it reaches or exceeds n, or if it proves impossible.
This C solution leverages a counting mechanism, iterating through the flowerbed and adding cushions (zeros) at the boundaries to simplify calculations. The number of available spots for planting is incrementally calculated and checked against n.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m), where m is the length of the flowerbed.
Space Complexity: O(1), only a constant amount of extra space is required.
| Approach | Complexity |
|---|---|
| Greedy Planting by Scanning | Time Complexity: O(m), where m is the length of the flowerbed array. |
| Counting Possible Placements | Time Complexity: O(m), where m is the length of the flowerbed. |
Can Place Flowers - Leetcode 605 - Python • NeetCode • 55,552 views views
Watch 9 more video solutions →Practice Can Place Flowers with our built-in code editor and test cases.
Practice on FleetCode