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.
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.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
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.
Which of these properties could exist for a graph but not a tree?
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
0to 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 second0) and end at index5(the second last0). - At index
1, the sum of the plot and its neighbors is0 + 1 + 0 = 1, which is not0. So we don't plant here. - At index
2, the sum is1 + 0 + 0 = 1, again not0. So we don't plant here. - At index
3, the sum is0 + 0 + 0 = 0, which is0. Here, all three plots are empty. We can plant a flower here by setting flowerbed[3] to1. The array becomes[0, 1, 0, 1, 0, 1, 0], and we decrementnby1. Now,n = 0.
- Conclusion: We continue the iteration, but since
nis0, it's clear we've managed to plant the required number of flowers without breaking the rule. There's no need to check index4and5, as we already planted all required flowers. - Final Check: Check
n. Sincenis now0, we returntrue, because it was possible to plant1flower 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
201class 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}
341class 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};
231// 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}
24Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?
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.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.