Leetcode – Can Place Flowers Solution in Python

Spread the love

Gardening has often been used as an analogy in programming problems, and the “Can Place Flowers” problem (#605) on Leetcode is no exception. This problem poses an intriguing array manipulation challenge that can be solved using a variety of approaches. In this article, we will delve deep into this problem, explore different methodologies to address it, and learn how to craft an elegant and efficient solution in Python.

Problem Statement

Let’s commence by understanding what the problem asks of us. The problem statement for Can Place Flowers is as follows:

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 if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Example:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true
Explanation: You can plant one flower in the third plot.

Approaches to Solve the Problem

1. Simple Iterative Approach

The brute force approach is to iterate through the flowerbed and, for each empty plot, check if it’s possible to plant a flower without violating the rule. We keep track of the number of flowers we can plant and compare it with the input n.

def canPlaceFlowers(flowerbed, n):
    # Length of the flowerbed array
    length = len(flowerbed)
    
    # Counter for the number of flowers that can be planted
    count = 0
    
    # Iterate through each plot in the flowerbed
    for i in range(length):
        # Check if current plot is empty
        if flowerbed[i] == 0:
            # Check the adjacent plots
            prev = 0 if i == 0 else flowerbed[i - 1]
            next = 0 if i == length - 1 else flowerbed[i + 1]
            
            # If both adjacent plots are empty, plant a flower
            if prev == 0 and next == 0:
                flowerbed[i] = 1
                count += 1
    
    # Check if we can plant at least n flowers
    return count >= n

Explanation:

  1. Iterate through each plot in the flowerbed.
  2. For each plot, check if it’s empty and if the adjacent plots are empty.
  3. Plant a flower and increment the counter if conditions are satisfied.
  4. Finally, check if the number of flowers that can be planted is greater than or equal to n.

Time Complexity:

This approach has a time complexity of O(N), where N is the length of the flowerbed array.

2. Optimized Iterative Approach

We can make a slight optimization to the above approach. If we have planted the required number of flowers before reaching the end of the flowerbed, we can terminate the loop early.

def canPlaceFlowers(flowerbed, n):
    length = len(flowerbed)
    count = 0

    for i in range(length):
        if flowerbed[i] == 0:
            prev = 0 if i == 0 else flowerbed[i - 1]
            next = 0 if i == length - 1 else flowerbed[i + 1]

            if prev == 0 and next == 0:
                flowerbed[i] = 1
                count += 1

        # Early termination if we have planted enough flowers
        if count >= n:
            return True

    return count >= n

This optimization doesn’t change the worst-case time complexity, but it can significantly reduce the running time for certain cases by avoiding unnecessary iterations.

Conclusion

The Can Place Flowers problem is an engaging example that demonstrates the importance of careful array manipulation and iteration. The key to solving this problem efficiently lies in understanding the constraints and optimizing the loop to avoid unnecessary iterations.

Leave a Reply