605. Can Place Flowers

[songyy5517]

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 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

Intuition This problem mainly examines the operations of arrays. We need to plant the flowers as many as possible under the adjacency rule, therefore we can use Greedy Algorithm to solve this problem. Specifically, we loop through the array and determine whether each position is plantable. If so, then we update the number of qualified positions, and set the value of this position to 1; If not, then just move to the next position.

[songyy5517]

Approach: Loop through the array & Greedy Algorithm

1. Exception Handling;
2. Define variable num_slot to store the number of the plantable positions;
3. Loop through the array, for each position: （1）If the position is isolated, then update the number of plantable position, and set the value of that position to 1; （2）Otherwise, just jump to the next position.
4. return the result of n <= num_slot .

Complexity Analysis

• Time complexity: $O(N)$ , looping through the array once costs the time of $O(N)$ ;
• Space complexity: $O(1)$ , additionally define constant-sized variables.

[songyy5517]

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        // Intuitioin: Find the slots that are isolated in the array.
        // 1. Exception handling
        if (flowerbed == null || flowerbed.length == 0 || n < 0)
            return false;

        // 2. Calculate the number of isolated slot
        int num_slot = 0;
        for (int i = 0; i < flowerbed.length; i++){
            if (flowerbed[i] == 0){
                if ((i > 0 && flowerbed[i - 1] == 1) || (i < flowerbed.length - 1 && flowerbed[i + 1] == 1))
                    continue;
                flowerbed[i] = 1;
                num_slot ++;
            }
        }

        return n <= num_slot;
    }
}

[songyy5517]

2024/5/8