Can plant flowers

Tag: Linkedin

Suppose 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 - they would compete for water and both would die.

Given a flowerbed (represented as an array containing booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule.

• test case 1
• 1, 0, 0, 0, 0, 0, 1, 0, 0
• 3 => true
• 4 => false

• test case 2
• 1, 0, 0, 1, 0, 0, 1, 0, 0
• 1 => true
• 2 => false

• test case 3
• 0
• 1 => true
• 2 => false

public boolean canPlaceFlowers(List<Boolean> flowerbed, int numberToPlace) {
    if (numberToPlace == 0) {
        return true;
    }

    if (flowerbed.size() == 1) {
        return !flowerbed.get(0) && numberToPlace <= 1;
    }
    // case 1: when index = 0, we can plant it if the second one is 0
    // case 2: when index = flowerbed.size() - 1, we can plant it if the previous one is 0
    // case 3: when it is in the middle, we can plant if the left and right is 0
    int counter = 0;
    for (int i = 0; i < flowerbed.size(); i++) {
        if (!flowerbed.get(i)) {
            if ((i == 0 && !flowerbed.get(i + 1))
                    || (i == flowerbed.size() - 1 && !flowerbed.get(i - 1))
                    || (!flowerbed.get(i - 1) && !flowerbed.get(i + 1))) {
                flowerbed.set(i, true);
                counter++;
                if (counter == numberToPlace) {
                    return true;
                }
            }
        }
    }
    return false;
}

Follow up: what if no random access to the list is permitted

check from the first possible plot to the last, store the current and next plots each time you iterate on a plot, which will separately become the previous and current plots when you iterate on the next plot.