Maarten van Beek

This post outlines a solution to the leetcode problem can-place-flowers.

The problem

The problem is layed out as follows:

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.

The analysis

We can break the problem in to 2 sub problems:

Determine the maximum amount of plots in which we can plant flowers
If this maximum amount is >= n return true and return false otherwise.

The second part is trivial, so we can focus on the first part. We can consider our input a string of 0's' interrupted by 1's. Any plants planted in one of these sub strings does not influence the capacity of any of the other sub strings, as none of the elements of different sub strings can be adjacent to one another. Therefore, the maximum amount of flowers we can plant is the sum of the maximum amount of plants we can plant in any of the sub strings. Therefore, all we have to do is determine the max amount of 1's we can put in a substring of zero's. This is simply half of the length of the substring, rounding up if there are an odd number of 0's

Resulting code

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
    let totalSum = 0;
    let partialSum = 0;

    let i = 0;

    while(i < flowerbed.length){
        const current = flowerbed[i];

        switch(current){
            case 0:
                partialSum += 1;
                break;
            case 1:
                const currentSum = Math.max(partialSum - 1, 0);
                totalSum += Math.ceil(currentSum/2);
                partialSum = 0
                i++;
                break;
        }

        i++;
    }

    const currentSum = Math.max(partialSum, 0);
    totalSum += Math.ceil(currentSum/2);
    return n <= totalSum;
};

Time complexity

O(n), where n is the amount of plots in the flowerbed.

Space complexity

O(1), We only use a static amount of variables totalSum, partiaSum, i, current, and currentSum. Where current and currentSum are reused every loop.