Can Place Flowers

Easy Arrays & Hashing Greedy Original on LeetCode

Can Place Flowers is a easy arrays & hashing problem solved with the greedy pattern. The best approach, optimal (single greedy pass), runs in O(m) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (rescan after every planting) up.

Problem

A long garden bed is described by an array flowerbed of 0s and 1s, where 1 means the plot already holds a flower and 0 means it is empty. Flowers must never be planted in two adjacent plots.

Given an integer n, return true if you can plant n new flowers in empty plots without breaking that rule, and false otherwise.

Examples

Example 1

Input
flowerbed = [0, 0, 1, 0, 0, 0, 0], n = 2
Output
true
Why
Plant at index 0 and index 5 (or index 6); none of them touch another flower.

Example 2

Input
flowerbed = [1, 0, 0, 0, 1, 0, 1], n = 2
Output
false
Why
Only index 2 is free on both sides, so at most one new flower fits.

Example 3

Input
flowerbed = [0], n = 1
Output
true
Why
A single empty plot has no neighbours at all.

Constraints

  • 1 <= flowerbed.length <= 2 * 10^4
  • flowerbed[i] is 0 or 1, and no two adjacent plots both hold a flower.
  • 0 <= n <= flowerbed.length

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (rescan after every planting)O(m · n)O(m)
Optimal (single greedy pass)O(m)O(1)

1Brute force (rescan after every planting)

TimeO(m · n)Each of up to n plantings may scan all m plots.
SpaceO(m)The copy of the bed.

Repeatedly scan the whole bed for any plot where a flower fits, plant it, and start over. Stop when n flowers are placed or a full scan finds nothing.

  1. Copy the bed so the input is not changed.
  2. While placed < n: scan all plots for a free one with free neighbours; if none, return false; else plant it and increment placed.
  3. Return true.
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int[] bed = flowerbed.clone();
        int m = bed.length;
        for (int placed = 0; placed < n; placed++) {
            int spot = -1;
            for (int i = 0; i < m && spot == -1; i++) {
                boolean leftFree = i == 0 || bed[i - 1] == 0;
                boolean rightFree = i == m - 1 || bed[i + 1] == 0;
                if (bed[i] == 0 && leftFree && rightFree) spot = i;
            }
            if (spot == -1) return false;
            bed[spot] = 1;
        }
        return true;
    }
}

2Optimal (single greedy pass)

TimeO(m)One pass over the m plots.
SpaceO(1)Only a counter and the previous plot's state; the input is not modified.

Walk left to right and plant in every plot that is empty with empty neighbours. Planting at the first possible spot is always safe, because any solution using a later spot in the same gap can be shifted left. Track the last planted flower with a variable instead of copying the bed.

  1. prev = state of the previous plot (0 before the start).
  2. For each i: if flowerbed[i] == 0, prev == 0 and the next plot is empty or missing, count one flower and set prev = 1; otherwise prev = flowerbed[i].
  3. Return true as soon as the count reaches n; at the end, return count >= n.
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int m = flowerbed.length, count = 0, prev = 0;
        for (int i = 0; i < m && count < n; i++) {
            int next = i == m - 1 ? 0 : flowerbed[i + 1];
            if (flowerbed[i] == 0 && prev == 0 && next == 0) {
                count++;
                prev = 1;
            } else {
                prev = flowerbed[i];
            }
        }
        return count >= n;
    }
}

Edge cases to test

  • n = 0 (always true)
  • Empty plots at the very start or end, which only have one neighbour
  • A bed of length 1
  • A long run of zeros: a run of k zeros between two flowers fits (k - 1) / 2

Hints

Hint 1

A plot can take a flower when it is empty and both neighbours (if they exist) are empty.

Hint 2

Planting as early as possible never hurts: an earlier flower only blocks plots you could not use together with it anyway.

Hint 3

Scan once, plant greedily, and stop as soon as you have placed n flowers.

FAQ

What is the best time complexity for Can Place Flowers?

Optimal (single greedy pass) runs in O(m) time and O(1) extra space. One pass over the m plots.

Which pattern does Can Place Flowers use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.

Is there a brute force solution for Can Place Flowers?

Yes. Brute force (rescan after every planting) takes O(m · n) time and O(m) space. Repeatedly scan the whole bed for any plot where a flower fits, plant it, and start over.

Which edge cases should I test for Can Place Flowers?

n = 0 (always true); Empty plots at the very start or end, which only have one neighbour; A bed of length 1; A long run of zeros: a run of k zeros between two flowers fits (k - 1) / 2.