605. Can Place Flowers

Problem Description

In this problem, you are given an array that represents a flowerbed, where each element in the array can either be 0 or 1. An element with a value of 0 implies that the corresponding plot in the flowerbed is empty, while an element with a value of 1 suggests that there is a flower already planted in that plot. The challenge is to plant new flowers (represented by n) in the empty plots under the condition that no two flowers can be adjacent to each other. If it's possible to plant n new flowers following this rule, you must return true, otherwise, you return false.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key to solving this problem is understanding that you can plant a flower in the current empty plot (i) only if both the preceding (i - 1) and following (i + 1) plots are also empty. This check ensures that no adjacent flowers rule is not violated.

Knowing this, we iterate through the flowerbed, and when we find an empty plot with empty adjacent plots, we plant a flower there by setting the current plot to 1 and decrementing n. To simplify the edge cases for the first and last plots in the flowerbed (which only have one neighbor), we can add a 0 at the start and end of the flowerbed array.

The process we follow is greedy because we plant a flower whenever we have a chance, which works since planting a flower sooner will never prevent us from planting another one later. If, by the end of this process, n is less than or equal to 0, it means we have successfully planted all the required flowers without breaking the rule and we return true. If not, it's impossible to plant all n flowers with the given constraints, so we return false.

Learn more about Greedy patterns.

Solution Approach

The solution utilizes a simple algorithm with a greedy approach. To implement this solution efficiently, we modify the original array to avoid checking for edge cases separately. We add a 0 at the beginning and at the end of the flowerbed array. This allows us to treat the first and last plots just like any other plot in the flowerbed without risking an out-of-bounds error when checking their neighbors.

After this initial preprocessing, we iterate through the modified flowerbed array starting from index 1 and ending one element before the last. At each plot (now index i), we check the value of the current plot as well as its immediate neighbors. We calculate the sum of the current plot and its neighbors: sum(flowerbed[i - 1 : i + 2]). If this sum is 0, it means all three consecutive plots (i - 1, i, and i + 1) are empty. In this case, we can safely plant a flower at the current position (i) by setting flowerbed[i] to 1 and decrementing n by 1 (representing planting one flower).

This loop continues till all the plots have been checked. If by the conclusion of the loop, n is less or equal to 0, it signifies that we have managed to plant all required n flowers in accordance with the rules, hence we return true. If n is still greater than 0, it implies that there wasn't enough space to plant all flowers while maintaining the non-adjacent condition, thus we return false.

This greedy approach works because by adding a flower at the earliest possible spot, we do not block any potential opportunities to add more flowers later on. Furthermore, planting a flower as soon as possible leaves us with the most options moving forward. This strategy ensures that our solution will find a valid configuration if one exists.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution approach with a small example. Suppose we are given the following flowerbed array and n:

flowerbed = [1, 0, 0, 0, 1], n = 1

Following the solution approach:

Preprocessing: First, we add a 0 to the start and end of the flowerbed. Now it becomes [0, 1, 0, 0, 0, 1, 0].
Iterating through the flowerbed:

We start iteration at index 1 (the second 0) and end at index 5 (the second last 0).
At index 1, the sum of the plot and its neighbors is 0 + 1 + 0 = 1, which is not 0. So we don't plant here.
At index 2, the sum is 1 + 0 + 0 = 1, again not 0. So we don't plant here.
At index 3, the sum is 0 + 0 + 0 = 0, which is 0. Here, all three plots are empty. We can plant a flower here by setting flowerbed[3] to 1. The array becomes [0, 1, 0, 1, 0, 1, 0], and we decrement n by 1. Now, n = 0.

Conclusion: We continue the iteration, but since n is 0, it's clear we've managed to plant the required number of flowers without breaking the rule. There's no need to check index 4 and 5, as we already planted all required flowers.
Final Check: Check n. Since n is now 0, we return true, because it was possible to plant 1 flower following the rules.

Hence, the function would return true indicating that we successfully planted the required number of flowers without any two being adjacent.

Solution Implementation

1class Solution:
2    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
3        # Add empty plots at the start and at the end of the flowerbed to simplify edge case handling
4        flowerbed = [0] + flowerbed + [0]
5      
6        # Iterate over each plot in the flowerbed starting from the first actual plot to the last
7        for i in range(1, len(flowerbed) - 1):
8            # Check if the current plot and its adjacent plots are empty
9            if sum(flowerbed[i - 1: i + 2]) == 0:
10                # Plant a flower in the current plot
11                flowerbed[i] = 1
12                # Decrement the count of flowers we need to plant
13                n -= 1
14                # If we have planted all required flowers, we can end early
15                if n == 0:
16                    return True
17      
18        # After checking all plots, decide if we were able to plant all flowers
19        return n <= 0
20

1class Solution {
2  
3    /**
4     * Determines if n flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.
5     * @param flowerbed An array representing the flowerbed where 0 is an empty spot and 1 is a spot with a flower.
6     * @param n The number of flowers we want to plant.
7     * @return True if we can plant n flowers, otherwise false.
8     */
9    public boolean canPlaceFlowers(int[] flowerbed, int n) {
10        // Get the length of the flowerbed array.
11        int length = flowerbed.length;
12      
13        // Iterate over all spots in the flowerbed.
14        for (int i = 0; i < length; ++i) {
15            // Check the spot to the left, it's 0 if we're at the first spot.
16            int left = i == 0 ? 0 : flowerbed[i - 1];
17            // Check the spot to the right, it's 0 if we're at the last spot.
18            int right = i == length - 1 ? 0 : flowerbed[i + 1];
19          
20            // If the current, left, and right spots are all empty (i.e., 0),
21            // then a flower can be planted at the current position.
22            if (left + flowerbed[i] + right == 0) {
23                // Plant the flower at the current position.
24                flowerbed[i] = 1;
25                // Decrease the remaining number of flowers to plant.
26                --n;
27            }
28        }
29      
30        // If n is less than or equal to 0, then all flowers have been successfully planted.
31        return n <= 0;
32    }
33}
34

1class Solution {
2public:
3    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
4        int flowerbedSize = flowerbed.size(); // Size of the flowerbed.
5      
6        // Iterate through the flowerbed to find valid spots to plant flowers.
7        for (int i = 0; i < flowerbedSize; ++i) {
8            // Check the left neighbor (if i is 0, left neighbor is considered empty).
9            int left = (i == 0) ? 0 : flowerbed[i - 1];
10            // Check the right neighbor (if i is the last element, right neighbor is considered empty).
11            int right = (i == flowerbedSize - 1) ? 0 : flowerbed[i + 1];
12          
13            // If both neighbors and current position are empty, we can plant a flower here.
14            if (left + flowerbed[i] + right == 0) {
15                flowerbed[i] = 1; // Plant a flower.
16                --n; // Decrease the count of flowers needed to plant.
17            }
18        }
19        // If n is less than or equal to 0, all flowers can be planted.
20        return n <= 0;
21    }
22};
23

1// Function to determine if 'n' new flowers can be planted in a flowerbed without violating the no-adjacent-flowers rule.
2function canPlaceFlowers(flowerbed: number[], n: number): boolean {
3    // Get the length of the flowerbed array.
4    const flowerbedLength = flowerbed.length;
5
6    // Loop through each spot in the flowerbed.
7    for (let i = 0; i < flowerbedLength; ++i) {
8        // Determine the state of the left spot (0 if at the start, otherwise the previous spot).
9        const leftNeighbor = i === 0 ? 0 : flowerbed[i - 1];
10        // Determine the state of the right spot (0 if at the end, otherwise the next spot).
11        const rightNeighbor = i === flowerbedLength - 1 ? 0 : flowerbed[i + 1];
12      
13        // Check if current spot and its neighbors are empty (0).
14        if (leftNeighbor + flowerbed[i] + rightNeighbor === 0) {
15            // Plant a flower at the current spot.
16            flowerbed[i] = 1;
17            // Decrease the count of flowers we need to plant.
18            --n;
19        }
20    }
21    // If we've managed to plant 'n' or more flowers, return true.
22    return n <= 0;
23}
24

Time and Space Complexity

The time complexity of the provided code is indeed O(n). This is because there is a single for-loop that iterates through the flowerbed list which contains n elements, and the operations inside the for-loop are performed in constant time.

For the space complexity, it would appear to be O(1) since we are not using any additional space that grows with the input size n. However, the list is extended at the beginning with two extra elements ([0] + flowerbed + [0]). Even though this operation doesn't depend on the size of the flowerbed, strictly speaking, the space complexity is O(n) because the input list itself is modified and could be considered as additional space being used relative to the original input list.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don't know