SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

This problem involves determining if a given number of new flowers (n) can be planted in an existing flowerbed without violating the rule that no two flowers can be planted in adjacent plots. The flowerbed is represented as an array where 1 indicates a plot that is already occupied and 0 indicates a vacant plot.

Intuition

The key observation here is that a flower can only be planted in a 0 plot if both the plots immediately before and after it are also 0 (or if it's at the boundary). As we traverse through the flowerbed array, whenever we find a suitable spot, we can place a flower and skip to the next potential spot by advancing the index.

Approach

1. Traverse the Array: Iterate through the flowerbed array.
2. Check Conditions: For each plot, check if it's 0 and if the adjacent plots (if they exist) are also 0.
3. Plant Flower: If the conditions are met, plant a flower (set the current plot to 1), skip the next plot (to avoid planting adjacent flowers), and decrease the count of flowers to be planted (n).
4. Early Exit: If at any point n becomes 0, return True immediately as we have successfully planted all flowers.
5. Final Check: After the loop, check if n is 0 or less, which indicates that all flowers were successfully planted.

Complexity

Time Complexity:

O(m) where m is the length of the flowerbed array. We traverse the array once.

Space Complexity:

O(1) since we use a constant amount of extra space (only variables for the index and flower count).

Code

C++

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        for (int i = 0; i < flowerbed.size(); i++) {
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.size() - 1 || flowerbed[i + 1] == 0)) {
                flowerbed[i] = 1;
                i++;
                n--;
            }
        }
        return n <= 0;
    }
};

Python

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

Java

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                flowerbed[i] = 1;
                i++;
                n--;
            }
        }
        return n <= 0;
    }
}

JavaScript

var canPlaceFlowers = function (flowerbed, n) {

    for (let i = 0; i < flowerbed.length; i++) {
        if (flowerbed[i] === 0 && !flowerbed[i - 1] && !flowerbed[i + 1]) {
            console.log(i, flowerbed[i]);
            i++;
            n--
        }
    }
    return n <= 0
};