Can Place flowers

XXX. Can Place Flowers

Array

Greedy

Problem Statement:

You have a long flowerbed in which some plots are planted, and some are not. However, flowers cannot be planted in adjacent plots. Given a flowerbed (represented as an array containing 0s and 1s) and a number n, return true if n new flowers can be planted without violating the no-adjacent-flowers rule.

Algorithm:

1. Iterate through the flowerbed array to check if a flower can be planted at each plot.
2. For a flower to be planted at position i:
   • The current plot (flowerbed[i]) must be empty (0).
   • The left plot (flowerbed[i - 1]) must either be out of bounds (i.e., i == 0) or also empty (0).
   • The right plot (flowerbed[i + 1]) must either be out of bounds (i.e., i == flowerbed.length - 1) or also empty (0).
3. If the above conditions are satisfied, plant a flower at position i by setting flowerbed[i] = 1 and decrement n.
4. At any point, if n reaches 0, return true.
5. If the loop completes and n > 0, return false.

Complexity:

Time Complexity: O(m), where m is the size of the flowerbed array. Each plot is checked once.
Space Complexity: O(1), as the algorithm modifies the input array in place without additional storage.

Java Implementation:

public boolean canPlaceFlowers(int[] flowerbed, int n) {
    // Edge case: If no flowers need to be planted, return true
    if (n == 0) return true;

    // Iterate through the flowerbed
    for (int i = 0; i < flowerbed.length; i++) {
        // Check if the current plot is empty and its neighbors (if any) are also empty
        if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) 
            && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
            flowerbed[i] = 1; // Plant a flower
            n--; // Decrement the count of flowers to be planted

            // If all flowers have been planted, return true
            if (n == 0) return true;
        }
    }

    // If unable to plant all flowers, return false
    return false;
}