Can Place Flowers

LeetCode 605 | Difficulty: Easy

Easy

Problem Description

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

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`.

- There are no two adjacent flowers in `flowerbed`.

- `0 <= n <= flowerbed.length`

Topics: Array, Greedy

---

Approach

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 195 ms)

Metric	Value
Runtime	195 ms
Memory	39.7 MB
Date	2022-01-10

Solution

public class Solution {
    public bool CanPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
    int l = flowerbed.Length;
    int prev = 0, next = 0;
    for (int i = 0; i < l && count < n; i++)
    {
        if(flowerbed[i] != 0) continue;
        prev = (i==0) ? 0 : flowerbed[i-1];
        next = (i==l-1) ? 0 : flowerbed[i+1];
        if(prev == 0 && next == 0) {
            flowerbed[i] = 1;
            count++;
        }       
    }
    return count >= n;
    }
}

📜 1 more C# submission(s)

Submission (2022-01-10) — 248 ms, 39.8 MB

public class Solution {
    public bool CanPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        int l = flowerbed.Length;
        for(int i=0;i<l;i++)
        {
            if(flowerbed[i]!=0) continue;
            if(i==0 && flowerbed[Math.Min(i+1, l-1)] == 0) { flowerbed[i]=1; count++; 
                                            }
            else if(i==l-1 && flowerbed[i-1] == 0) { flowerbed[i]=1;count++; }
            else if(i>0 && i<l-1 && flowerbed[i-1] == 0 && flowerbed[i+1] == 0)  { flowerbed[i]=1;count++; }
            if(count == n) return true;
        }
        
        return count >= n;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.