Can Place Flowers

Easy
199.

Can Place Flowers

Can Place Flowers is an easy coding problem on arrays and greedy, asked in Amazon, Microsoft, Adobe and Atlassian interviews.

You have a long flowerbed in which some plots are planted and some are not. Flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0s (empty) and 1s (planted), and an integer n, return true if n new flowers can be planted without violating the adjacency rule.

Example 1

Input
flowerbed = [1,0,0,0,1], n = 1
Output
true
Explanation
The middle plot can take one flower.

Example 2

Input
flowerbed = [1,0,0,0,1], n = 2
Output
false

Example 3

Input
flowerbed = [0,0,1,0,0], n = 2
Output
true

Constraints

  • 1 <= flowerbed.length <= 40
  • flowerbed[i] is 0 or 1.
  • There are no two adjacent flowers in the input.
  • 0 <= n <= 20
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Can Place Flowers — Solution in Python, Java & C++

Can Place Flowers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and greedy.

Can Place Flowers is an easy coding problem on arrays and greedy, asked in Amazon, Microsoft, Adobe and Atlassian interviews.

Problem statement

You have a long flowerbed in which some plots are planted and some are not. Flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0s (empty) and 1s (planted), and an integer n, return true if n new flowers can be planted without violating the adjacency rule.

Example 1

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true
Explanation: The middle plot can take one flower.

Example 2

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

Example 3

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

Constraints

  • 1 <= flowerbed.length <= 40
  • flowerbed[i] is 0 or 1.
  • There are no two adjacent flowers in the input.
  • 0 <= n <= 20

Hints for Can Place Flowers

  1. Hint 1

    Scan left to right and plant greedily whenever a plot is empty and both neighbours are empty.

  2. Hint 2

    Treat positions before the start and after the end as empty, so the two ends are not special cases in disguise.

  3. Hint 3

    Planting as early as possible is optimal — an earlier flower never blocks more plots than a later one.

How to solve Can Place Flowers

Greedy left to right: plant in any empty plot whose neighbours are empty, treating out-of-range positions as empty.

Approach

  1. Walk the bed; at i, plant if bed[i] == 0, i == 0 or bed[i-1] == 0, and i == last or bed[i+1] == 0.
  2. Mark the plot planted and count.
  3. Return planted >= n.

Why it works

Planting at the earliest legal plot never hurts: it blocks only i + 1, and any optimal arrangement that skips i for i + 1 can swap to i without losing a flower. Repeating the exchange shows greedy is maximal.

Complexity

  • Time — O(n)
  • Space — O(1) if mutating a copy

Pitfalls

  • Forgetting to mark the plot after planting lets the next plot plant adjacent to it.
  • Stop early once planted >= n if you like — the count only grows.

Reference solution

Python

def canPlaceFlowers(flowerbed, n) -> bool:
    bed = list(flowerbed)
    planted = 0
    for i in range(len(bed)):
        if bed[i] == 0 and (i == 0 or bed[i - 1] == 0) and (i == len(bed) - 1 or bed[i + 1] == 0):
            bed[i] = 1
            planted += 1
    return planted >= n

Java

public static boolean canPlaceFlowers(int[] flowerbed, int n) {
    int[] bed = Arrays.copyOf(flowerbed, flowerbed.length);
    int planted = 0;
    for (int i = 0; i < bed.length; i++) {
        if (bed[i] == 0 && (i == 0 || bed[i - 1] == 0) && (i == bed.length - 1 || bed[i + 1] == 0)) {
            bed[i] = 1;
            planted++;
        }
    }
    return planted >= n;
}

C++

bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    vector<int> bed = flowerbed;
    int planted = 0;
    int len = (int) bed.size();
    for (int i = 0; i < len; i++) {
        if (bed[i] == 0 && (i == 0 || bed[i - 1] == 0) && (i == len - 1 || bed[i + 1] == 0)) {
            bed[i] = 1;
            planted++;
        }
    }
    return planted >= n;
}

JavaScript

var canPlaceFlowers = function(flowerbed, n) {
    const bed = flowerbed.slice();
    let planted = 0;
    for (let i = 0; i < bed.length; i++) {
        if (bed[i] === 0 && (i === 0 || bed[i - 1] === 0) && (i === bed.length - 1 || bed[i + 1] === 0)) {
            bed[i] = 1;
            planted++;
        }
    }
    return planted >= n;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms