Problem 14 - Can Place Flowers

Explore our archive for previous posts.

Question

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

Constraints:

• 1 <= flowerbed.length <= 2 * 104

• flowerbed[i] is 0 or 1.

• There are no two adjacent flowers in flowerbed.

• 0 <= n <= flowerbed.length

Approach

The solution iterates through the flowerbed array, checking each spot for availability to plant a flower. It maintains a count of the planted flowers and stops iterating when the count reaches the desired number. It considers the previous and next spots of the current spot to ensure they are also empty. If all conditions are met, a flower is planted and the count is incremented. Finally, it checks if the count of planted flowers matches the required number and returns the result.
Here are the detailed steps:

• You iterate through the flowerbed array using a for loop and keep track of the count of planted flowers.

• For each position, you check if the current element is 0, indicating an empty spot.

• You also check the adjacent elements by accessing flowerbed[i - 1] and flowerbed[i + 1], taking care of the boundary cases to avoid index out of bounds.

• If the previous and next elements are both 0, indicating empty spots, you plant a flower by setting flowerbed[i] to 1 and increment the count.

• Finally, you check if the count of planted flowers is equal to the required number of flowers, n, and return the result accordingly.

Solution

Solve it here

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0; // Counter to keep track of planted flowers
        
        for (int i = 0; i < flowerbed.length && count < n; i++) {
            if (flowerbed[i] == 0) { // Check if current spot is empty
                int prev = (i == 0) ? 0 : flowerbed[i - 1]; // Get value of previous spot
                int next = (i == flowerbed.length - 1) ? 0 : flowerbed[i + 1]; // Get value of next spot
                
                if (prev == 0 && next == 0) { // Check if previous and next spots are also empty
                    flowerbed[i] = 1; // Plant a flower
                    count++; // Increment the count of planted flowers
                }
            }
        }
        
        return count == n; // Check if the required number of flowers is planted
    }
}

Time and space complexity

Time Complexity: The time complexity of the given solution is O(n), where n is the length of the flowerbed array. This is because it iterates through each element of the array once.

Space Complexity: The space complexity of the solution is O(1) because it uses a constant amount of additional space. It does not use any data structures or variables that grow with the input size.