C++ Solution to Leetcode 605. Can Place Flowers

Problem statement

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.

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.

Solution: Check the no-adjacent-flowers rule

A new flower can be planted at the position i only if

flowerbed[i - 1] == 0 && flowerbed[i] == 0 && flowerbed[i + 1] == 0.

If the condition is satisfied, the flower can be planted at the position i. flowerbed[i] is now assigned to 1. Then you can skip checking the rule for the position i + 1 and go directly to the position i + 2.

Code

#include <iostream>
#include <vector>
using namespace std;
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    if (n == 0) {
        return true;
    }
    flowerbed.insert(flowerbed.begin(), 0);
    flowerbed.push_back(0);
    int i = 1;
    while (i < flowerbed.size() - 1) {
        if (flowerbed[i - 1] == 0 && flowerbed[i] == 0 && flowerbed[i + 1] == 0) {
            flowerbed[i] = 1;
            n--;
            i+=2;
        } else {
            i++;
        }
    }
    return false;
}
int main() {
    vector<int> flowerbed{1,0,0,0,1};
    cout << canPlaceFlowers(flowerbed, 1) << endl;
    flowerbed = {1,0,0,0,1};
    cout << canPlaceFlowers(flowerbed, 2) << endl;
}

Output:
1
0

Complexity

Runtime: O(N), where N = flowerbed.length.
Extra space: O(1).

Implementation note

In this implementation, you could insert an element 0 to the front and the back of the vector flowerbed to avoid writing extra code for checking the no-adjacent-flowers rule at i = 0 and i = flowerbed.size() - 1.
There are a few ways to insert an element into a vector. Here you can see an example of using the methods insert and push_back of a std::vector.

What is your approach? The problem was picked from leetcode.com. You can submit your solution in any programming language and check the performance.

Thanks for reading. Feel free to share your thought about my content and check out my FREE book 10 Classic Coding Challenges.

605. Can Place Flowers

Comments

More from this blog

Leetcode 59. How To Go Around A Square Matrix In Spiral Order

Leetcode 120. How To Find The Minimum Path From Top To Bottom Of A Triangle

How To Find The Longest Substring Without Repeating Characters

How To Find The Maximal Subarray Having Distinct Elements

Common Mistakes in Coding Interviews and How to Avoid Them

Problem statement

Example 1

Example 2

Constraints

Solution: Check the no-adjacent-flowers rule

Code

Complexity

Implementation note

Command Palette

Comments

More from this blog

Problem statement

Example 1

Example 2

Constraints

Solution: Check the no-adjacent-flowers rule

Code

Complexity

Implementation note