**Problem:**

Please find the problem here.

**Solution:**

The key hint in this problem is that it is an easy problem. That lead me to think about greedy algorithm.

The idea is simple, we simply start from the left and plant a flower whenever we can. The key challenge, however, is to prove that this idea is optimal.

**Analysis:**

**We will use the greedy algorithm stay ahead method.**

First, we know that there exist an optimal solution, we claim that our greedy algorithm is going to be at least as good as the optimal algorithm for every prefix.

It is obvious for prefix of length 0, both of them has planted 0 plants.

Assuming the invariant held for all prefixes of length $ k $. Is it possible for the greedy algorithm to lose for $ k + 1 $?

For the sake of argument, we assume that the optimal wins at position $ k + 1 $. The only possibility for $ k + 1 $ to win is that in the optimal solution we planted but in the greedy algorithm we didn't.

Note that if the optimal solution can plant in location $ k + 1 $, then the location $ k $ and $ k + 2 $ must be empty (initially and also in the optimal solution)

The only reason that the greedy algorithm cannot plant in location $ k + 1 $ is because $ k $ is already planted. But we already argued that in the optimal solution location $ k $ is empty in the optimal solution, so we have a situation like this

k (k + 1)

Greedy planted not planted

Optimal not planted planted

So the number of plants in both greedy and optimal is the same for the last two, but we already knew that any prefixes cannot win, so the fact that the optimal solution wins at position $ k + 1 $ is a contradiction.

The contradiction shows that any prefix of the greedy solution is better than the optimal. Since the whole problem is also a prefix, now we have just shown the correctness of the greedy algorithm!

**Code:**

#include "stdafx.h" // https://leetcode.com/problems/can-place-flowers #include "LEET_CAN_PLACE_FLOWERS.h" #include <map> #include <iostream> #include <sstream> #include <vector> #include <string> using namespace std; namespace _LEET_CAN_PLACE_FLOWERS { class Solution { public: bool canPlaceFlowers(vector<int>& flowerbed, int n) { for (size_t i = 0; i < flowerbed.size(); i++) { if (n == 0) { break; } else { if ((i == 0 || flowerbed[i - 1] == 0) && flowerbed[i] == 0 && ((i == flowerbed.size() - 1) || flowerbed[i + 1] == 0)) { flowerbed[i] = 1; n--; } } } return n == 0; } }; }; using namespace _LEET_CAN_PLACE_FLOWERS; int LEET_CAN_PLACE_FLOWERS() { Solution solution; int test_array[] = { 1, 0, 0, 0, 1 }; vector<int> test(test_array, test_array + _countof(test_array)); cout << solution.canPlaceFlowers(test, 1) << endl; return 0; }