Sponsored
Sponsored
This 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.
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.
1public class Solution {
2 public bool CanPlaceFlowers(int[] flowerbed, int n) {
3 for (int i = 0; i < flowerbed.Length; i++) {
4 if (flowerbed[i] == 0) {
5 bool isPrevEmpty = (i == 0) || (flowerbed[i - 1] == 0);
6 bool isNextEmpty = (i == flowerbed.Length - 1) || (flowerbed[i + 1] == 0);
7 if (isPrevEmpty && isNextEmpty) {
8 flowerbed[i] = 1;
9 n--;
10 if (n == 0) return true;
11 }
12 }
13 }
14 return n <= 0;
15 }
16}This C# solution is analogous to previous solutions, iterating through the flowerbed to place flowers if possible. It leverages the C# array handling features to manage boundary cases effortlessly while planting flowers where conditions allow.
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.
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.
1using namespace std;
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int count = 0, consecutiveZeros = 1; // extra zero before start
for (int plot : flowerbed) {
if (plot == 0) {
consecutiveZeros++;
} else {
count += (consecutiveZeros - 1) / 2;
consecutiveZeros = 0;
}
}
count += consecutiveZeros / 2; // extra zero at the end
return count >= n;
}
};This C++ solution uses a counting approach through the flowerbed, effectively calculating the potential flower placements within consecutive zeros. The edge zeros at the start and end help in handling boundary planting.