Can Place Flowers

LeetCode 75

Introduction

Continuing my journey of writing daily blogs, today I tackled another interesting problem from LeetCode 75: Can Place Flowers. This problem involves determining if a certain number of new flowers can be planted in a flowerbed without violating the rule that no two flowers can be adjacent. Let's explore the problem statement, approach, and solution in detail.

Problem Statement

You have a long flowerbed represented by an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty. Flowers cannot be planted in adjacent plots. Given the array flowerbed and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule, and false otherwise.

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 * 10^4

• flowerbed[i] is 0 or 1.

• There are no two adjacent flowers in the flowerbed.

• 0 <= n <= flowerbed.length

Approach to Solve the Problem

To solve this problem, we need to check each position in the flowerbed to see if we can plant a flower without violating the rule. Here are the steps involved:

1. Handle Edge Case: If the flowerbed has only one plot and it's empty, we can plant a flower if n is 1.

2. Iterate Through Flowerbed: Loop through each plot in the flowerbed.

3. Check Planting Conditions: For each empty plot (0), check if the adjacent plots are also empty or if it's at the boundary of the flowerbed.

4. Plant Flower: If the conditions are met, plant a flower by setting the plot to 1 and decrement n.

5. Early Termination: If all flowers are planted before reaching the end of the flowerbed, break the loop and return true.

Solution

Here's the Java code that implements the above approach:

public static boolean canPlaceFlowers(int[] flowerbed, int n) {
    int len = flowerbed.length;

    // considering the edge case if array has only one element and it's 0
    if(len == 1 && flowerbed[0] == 0){
        return true;
    }

    for(int i = 0; i < len; i++){

        // break the loop if all flowers are planted
        if(n == 0){
            break;
        }

        // if the position is vacant at 0 index
        if(flowerbed[i] == 0){
            if(i == 0){
                if(flowerbed[i+1] == 0){
                    flowerbed[i] = 1;
                    n--;
                }
            }
            // if the position is vacant at last index
            else if(i == len-1){
                if(flowerbed[i-1] == 0){
                    flowerbed[i] = 1;
                    n--;
                }
            }
            // other remaining positions
            else{
                if(flowerbed[i-1] == 0 && flowerbed[i+1] == 0){
                    flowerbed[i] = 1;
                    n--;
                }
            }

        }
    }

    return n == 0;
}

Explanation

1. Edge Case Handling: If the flowerbed has only one plot and it's empty, we can plant a flower if n is 1.

2. Loop Through Flowerbed: We iterate through each plot to check if we can plant a flower.

3. Planting Conditions: We check if the current plot and its adjacent plots are empty or if it's a boundary plot.

4. Plant Flower: If conditions are met, we plant a flower and decrement n.

5. Early Termination: If all required flowers are planted, we break the loop and return true.

Conclusion

This solution efficiently checks each plot in the flowerbed to determine if new flowers can be planted without violating the no-adjacent-flowers rule. Array manipulation problems like these are fundamental in programming and help build a strong foundation for solving more complex challenges.

I hope you found this explanation helpful. Stay tuned for more daily blogs on interesting problems and concepts I encounter in my learning journey!