LeetCode75 : Can Place Flowers

Introduction

The Can Place Flowers problem is a classic greedy algorithm challenge frequently featured in coding interviews and study plans like LeetCode 75. In this problem, you’re given a binary list called flowerbed where 0 represents an empty plot and 1 represents a plot with a flower already planted. Along with this, you’re given an integer n, representing the number of new flowers you want to plant.

The twist is that no two flowers can be planted in adjacent plots—meaning you must ensure that each new flower has at least one empty space between it and any neighboring flower. Your task is to determine whether it’s possible to plant n new flowers in the flowerbed without violating this rule.

You have a flowerbed represented as a list of 0s and 1s, where:

• 0 means an empty plot.
• 1 means a flower is already planted.

You are also given an integer n, representing the number of new flowers you want to plant.

Rule:
Flowers cannot be planted in adjacent plots. That is, no two flowers can be planted next to each other.

Task:

Determine if n new flowers can be planted without violating the no-adjacent-flowers rule.

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 * 10^4
• flowerbed[i] is 0 or 1
• flowerbed does not contain two adjacent 1s
• 0 <= n <= flowerbed.length

Python Solution

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        i = 0
        while i < len(flowerbed):
            if flowerbed[i] == 0:
                if i == len(flowerbed) - 1 or flowerbed[i + 1] == 0:
                    n -= 1
                    i += 2
                else:
                    i += 1
            else:
                i += 2
        return n <= 0

Step-by-Step Explanation

Step 1: Initialize Index Pointer

i = 0

• Start from the beginning of the flowerbed array.
• i will be used to iterate through each plot.

Step 2: Loop Through the Flowerbed

while i < len(flowerbed):

• Continue until you’ve checked all plots.

Step 3: Check for Empty Plot

if flowerbed[i] == 0:

• If the current plot is empty, we consider planting a flower.

Step 4: Check Next Plot (or Edge Case)

if i == len(flowerbed) - 1 or flowerbed[i + 1] == 0:

• If this is the last plot OR the next plot is also empty, then planting is allowed (no adjacent flowers).
• Reduce n since one flower is planted.
• Skip the next plot by moving i += 2.

Step 5: Else Skip One Plot

else:
    i += 1

• If the next plot is not empty, we can’t plant here, so move to the next one.

Step 6: Already Occupied? Skip Next

else:
    i += 2

• If the current plot already has a flower (1), skip the next one to maintain the no-adjacent rule.

Step 7: Return Result

return n <= 0

• If n is 0 or less, return True (successfully planted all).
• Else, return False.

Time and Space Complexity

• Time Complexity:O(n)
  • We traverse the flowerbed list once.
• Space Complexity:O(1)
  • No extra space is used, just variables.

This solution uses a greedy and linear scan approach to check where flowers can be planted, making sure to skip adjacent plots as needed. It ensures no flower is placed where the rule is violated and handles edge cases effectively.

Related Read

LeetCode75: Kids With the Greatest Number of Candies