LeetCode 605: Can Place Flowers Solution in Python – A Step-by-Step Guide

What Is LeetCode 605: Can Place Flowers?

In LeetCode 605: Can Place Flowers, you’re given a flowerbed as an array of 0s (empty) and 1s (flowers), and an integer n representing how many new flowers you want to plant. You can plant a flower in an empty spot (0) only if its adjacent spots (left and right) are also empty (or don’t exist, like at the ends). Your task is to determine if you can plant all n flowers without breaking the no-adjacent-flowers rule. For example, in [1,0,0,0,1], you can plant 1 flower at index 2 (middle 0), but not more. This problem tests your ability to handle array constraints and optimize placement.

Problem Statement

• Input:
• flowerbed: List of integers (0s and 1s).
• n: Integer (number of flowers to plant).
• Output: Boolean—True if n flowers can be planted, False otherwise.
• Rules:
• Can’t plant where a flower (1) already exists.
• No two flowers can be adjacent (left or right).

Constraints

• 1 <= flowerbed.length <= 2 * 10⁴.
• flowerbed[i] is 0 or 1.
• No adjacent 1s in the initial flowerbed.
• 0 <= n <= 10⁴.

Examples

• Input: flowerbed = [1,0,0,0,1], n = 1
• Output: True (Plant at index 2)
• Input: flowerbed = [1,0,0,0,1], n = 2
• Output: False (Only 1 spot available)
• Input: flowerbed = [0,0,1,0,0], n = 2
• Output: True (Plant at 0 and 4)

These examples hint at a pattern—let’s solve it!

Understanding the Problem: Planting Flowers with Gaps

To solve LeetCode 605: Can Place Flowers in Python, we need to scan a flowerbed array and count how many new flowers we can plant, ensuring no two are adjacent, then check if that’s enough for n. A brute-force approach might try every combination, but that’s overkill. Instead, we’ll use:

• Best Solution (Greedy Single-Pass): O(n) time, O(1) space—fast and simple.
• Alternative Solution (Two-Pointer Simulation): O(n) time, O(1) space—visual but more steps.

Let’s start with the greedy solution, breaking it down for beginners.

Best Solution: Greedy Approach with Single-Pass Counting

Why This Is the Best Solution

The greedy single-pass approach is the top choice for LeetCode 605 because it’s efficient—O(n) time and O(1) space—and elegantly counts plantable spots in one sweep. It leverages the fact that we can maximize placements by planting as early as possible while respecting the no-adjacent rule. It’s like walking through the flowerbed, planting wherever you can without looking back!

How It Works

Think of this as strolling through the garden:

• Step 1: Handle Edges:
• At the start, check how many 0s before the first 1 (or end).
• At the end, check 0s after the last 1.
• Step 2: Count Gaps:
• Between 1s, count consecutive 0s.
• For k consecutive 0s, you can plant (k-1)//2 flowers (middle spots).
• Step 3: Total and Compare:
• Sum all plantable spots.
• Return True if >= n.
• Step 4: Why Greedy Works:
• Planting early maximizes future options (given no initial adjacent 1s).

It’s like spotting plantable gaps on the fly!

Step-by-Step Example

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

• Init: count = 0.
• Edges:
• Start: [1,...], no 0s before 1, 0 flowers.
• End: [...,1], no 0s after last 1, 0 flowers.
• Gaps:
• Between 1s: [0,0,0], 3 zeros.
• Plantable = (3-1)//2 = 1.
• count = 1.
• Check: count = 1 >= n = 1, True.

Example: flowerbed = [0,0,1,0,0], n = 2

• Edges:
• Start: [0,0,1,...], 2 zeros, count = 2//2 = 1.
• End: [...,1,0,0], 2 zeros, count += 2//2 = 1.
• Gaps: No inner gaps (only one 1).
• Total: count = 2.
• Check: 2 >= 2, True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        # Step 1: Initialize variables
        length = len(flowerbed)
        count = 0  # Total plantable flowers
        i = 0      # Current index

        # Step 2: Process flowerbed
        while i < length:
            if flowerbed[i] == 1:
                i += 1  # Skip flower
            else:
                # Count consecutive zeros
                left = i - 1
                right = i + 1
                # Check left and right neighbors
                left_empty = left < 0 or flowerbed[left] == 0
                right_empty = right >= length or flowerbed[right] == 0

                if left_empty and right_empty:
                    flowerbed[i] = 1  # Plant here
                    count += 1
                    i += 1  # Move past planted spot
                i += 1

        # Step 3: Check if enough flowers can be planted
        return count >= n

• Lines 4-6: Setup:
• length: Array size.
• count: Tracks plantable spots.
• i: Current position.
• Lines 9-20: Process:
• If 1, skip.
• If 0, check left and right:
• Left empty if at start or 0.
• Right empty if at end or 0.
• If both empty, plant (set to 1), increment count.
• Line 23: Return True if count >= n.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—no extra space.

This is like a garden sweep—plant and count fast!

Alternative Solution: Two-Pointer Simulation

Why an Alternative Approach?

The two-pointer simulation tracks stretches of zeros with pointers—O(n) time, O(1) space. It’s more visual, explicitly counting zeros between 1s or at edges, but involves more steps than the greedy method. It’s like using a measuring tape to check each gap!

How It Works

Picture this as measuring empty stretches:

• Step 1: Use two pointers to find gaps of 0s.
• Step 2: For each gap:
• At start: zeros // 2.
• Between 1s: (zeros - 1) // 2.
• At end: zeros // 2.
• Step 3: Sum plantable flowers.
• Step 4: Compare with n.

It’s like pacing out plantable zones!

Step-by-Step Example

Example: flowerbed = [0,0,1,0,0], n = 2

• Start: [0,0,1,...], 2 zeros, count = 2//2 = 1.
• Middle: [1,0,0], 0 zeros (no gap), count += 0.
• End: [...,1,0,0], 2 zeros, count += 2//2 = 1.
• Total: count = 2.
• Check: 2 >= 2, True.

Code for Two-Pointer Approach

Copy codeclass Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        length = len(flowerbed)
        count = 0
        prev = -2  # Far left to handle start

        for i in range(length):
            if flowerbed[i] == 1:
                zeros = i - prev - 1
                if prev == -2:  # Start gap
                    count += zeros // 2
                else:  # Middle gap
                    count += (zeros - 1) // 2
                prev = i

        # Handle end gap
        zeros = length - prev - 1
        if prev == -2:  # All zeros
            count += (zeros + 1) // 2
        else:  # End gap
            count += zeros // 2

        return count >= n

• Lines 5-14: Process gaps:
• prev: Last 1’s index.
• On 1, calculate zeros since last 1.
• Adjust for start or middle.
• Lines 16-20: End gap:
• Calculate zeros after last 1.
• Adjust for all-zeros case.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—just pointers.

It’s a gap-measuring stroll!

Comparing the Two Solutions

• Greedy (Best):
• Pros: O(n) time, O(1) space, simple and fast.
• Cons: Modifies array (can avoid if needed).
• Two-Pointer (Alternative):
• Pros: O(n) time, O(1) space, explicit gap counting.
• Cons: More logic steps.

Greedy wins for elegance.

Additional Examples and Edge Cases

• Input: [0], n = 1
• Output: True.
• Input: [1,0,1], n = 1
• Output: False.

Both handle these well.

Complexity Breakdown

• Greedy: Time O(n), Space O(1).
• Two-Pointer: Time O(n), Space O(1).

Both are efficient.

Key Takeaways

• Greedy: Plant early—smart!
• Two-Pointer: Measure gaps—clear!
• Arrays: Constraints are fun.
• Python Tip: Loops shine—see Python Basics.

Final Thoughts: Plant Those Flowers

LeetCode 605: Can Place Flowers in Python is a fun array challenge. The greedy approach offers speed and simplicity, while two-pointers give a visual twist. Want more? Try LeetCode 283: Move Zeroes or LeetCode 665: Non-decreasing Array. Ready to garden? Head to Solve LeetCode 605 on LeetCode and plant those flowers today!