605. Can Place Flowers
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 if n
new flowers can be planted in the flowerbed
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
Constraints:
1 <= flowerbed.length <= 2 * 104
flowerbed[i]
is0
or1
.- There are no two adjacent flowers in
flowerbed
. 0 <= n <= flowerbed.length
Solution :-
Two Solution :-
1) By modifying vectore :
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
flowerbed.insert(flowerbed.begin(),0);
flowerbed.push_back(0);
for(int i = 1; i < flowerbed.size()-1; ++i)
{
if(flowerbed[i-1] + flowerbed[i] + flowerbed[i+1] == 0)
{
n--;
++i;
}
}
return n <=0;
}
};
2) With out modifying vector :
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int m = flowerbed.size() , count=0 , i=0;
while(i<m-1)
{
//checking two adjacent position and maintaining variable i accordingly
if(!flowerbed[i] && !flowerbed[i+1]){
count++;
i += 2;
}
else if(flowerbed[i]==1)
i += 2;
else if(flowerbed[i+1]==1)
i += 3;
}
// checking for last index in case n is odd
if(i<m && flowerbed[i]==0)
count++;
return count>=n;
}
};
Time Complexity :- O(N)
Space Complexity - O(1)
0 Comments