Can Place Flowers - Leetcode Solution

Problem Statement:

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.

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.

Solution:

In this problem, we need to check whether we can place n flowers in the given flowerbed without violating the no-adjacent-flowers rule. The simplest approach would be to brute force all possible combinations of positions for the flowers and check if there are no adjacent flowers. However, this approach has a time complexity of O(2^N) which is not feasible for large arrays.

A better approach would be to iterate over the elements in the array and check if the current element is 0. If the current element is 0, then we need to check if the previous and next elements are also 0. If they are, then we can plant a flower at the current position and decrement n. We can continue this process until either we have planted all n flowers or we have iterated over all the elements in the flowerbed.

Algorithm:

1. Initialize a counter variable 'n' to the number of flowers that needs to be placed.
2. Iterate over the elements in the flowerbed from index '1' to 'n-1'. a. If the current element is '0', the previous element is '0' and the next element is '0', then plant a flower at the current position. b. Decrease the value of 'n' by 1.
3. If the value of 'n' is '0', then return True, else False.

Code:

Here is the Python code that implements the above algorithm:

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        if n == 0:
            return True
        if len(flowerbed) == 1:
            if flowerbed[0] == 0 and n <= 1:
                return True
            else:
                return False
        for i in range(len(flowerbed)):
            if flowerbed[i] == 0:
                if i > 0 and flowerbed[i-1] == 1:
                    continue
                if i < len(flowerbed) - 1 and flowerbed[i+1] == 1:
                    continue
                flowerbed[i] = 1
                n -= 1
                if n == 0:
                    return True
        return False

Time Complexity:

The time complexity of this approach is O(N), where N is the length of the input array.

Space Complexity:

The space complexity of this approach is O(1) as we only use constant extra space.

1