What is the brute force approach and complexity for Can Place Flowers?

Check every set of plots and keep one that is valid and big enough with time complexity O(N · 2^N) and space complexity O(1).

What is the optimal approach and complexity for Can Place Flowers?

Scan left to right; plant wherever the plot and both neighbours are empty, then skip the next plot with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Can Place Flowers?

Look for key signals in the prompt: "flowers cannot be planted in adjacent plots" indicates Each flower blocks its neighbours, so a choice at one plot changes which plots are open next.; "plant n new flowers" indicates We only need to reach `n`, so the question is how many flowers fit at most.; "return true or false" indicates If the most we can plant is at least `n`, the answer is `true`..

Can Place Flowers

Easy·LeetCode #605 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

A row of flowerbed plots is given. Each plot either already has a flower (1) or is empty (0). Flowers cannot be planted next to each other, so a new flower can only go on an empty plot whose neighbours are both empty. A missing neighbour (at the start or the end of the row) counts as empty.

Given the row and a number n, return true if you can plant n new flowers without breaking this rule, and false otherwise.

Input

An array flowerbed of 0 and 1 values, and a number n. The row already obeys the rule: no two flowers are next to each other.

Output

true if at least n new flowers fit, otherwise false.

Example 1

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

Output: true

Plant on index 2. Its neighbours, index 1 and index 3, are both empty.

Example 2

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

Output: false

Index 1 touches the flower at index 0, and index 3 touches the flower at index 4. Only index 2 is safe, so only one flower fits.

Constraints

• 1 ≤ flowerbed.length ≤ 2 · 10^4
• Each value in flowerbed is 0 or 1.
• No two flowers in flowerbed are next to each other.
• 0 ≤ n ≤ flowerbed.length

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“flowers cannot be planted in adjacent plots”

→ Each flower blocks its neighbours, so a choice at one plot changes which plots are open next.

“plant n new flowers”

→ We only need to reach `n`, so the question is how many flowers fit at most.

“return true or false”

→ If the most we can plant is at least `n`, the answer is `true`.

Approach Complexity Ladder

Brute Force — try every set of plotsO(N · 2^N)O(1)

Check every set of plots and keep one that is valid and big enough

Optimal — plant on the first free plot, skip the nextO(N)O(1)

Scan left to right; plant wherever the plot and both neighbours are empty, then skip the next plot

Brute Force Intuition

Each plot can be planted or left empty, so there are 2^N sets of plots. For each set, check that every chosen plot is empty and that no chosen plot touches a flower or another chosen plot. If any valid set has at least n flowers, return true.

Recognition rule for this sub-pattern:

Keep a running balance; when it fails, the start must move past this point. Two passes handle left and right rules.

Remember this · Greedy

Trigger

Maximise count / minimise cost with a natural "best next step", sorting makes the choice obvious, reachability.

Think

Is there a choice I can always make safely without looking ahead?

Key question

Why can't the greedy choice be worse than the optimal one? (Try to break it with a small example.)

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Greedy translate into production architectures and low-level memory mechanics.

LLD Architecture