Can Place Flowers

In this article, we will explore three different approaches to tackle this problem. Each approach progressively improves upon the previous one, aiming to minimize unnecessary checks and iterations while still ensuring accurate results.

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 and false otherwise.

Let’s dive into the details of each approach and explore how they provide distinct perspectives and optimizations to address the problem efficiently.

Approach 1: Brute Force

1. In this approach, we check for all the possible positions of planting flowers.

2. We iterate through the flowerbed and for each position, we check if the current position and its adjacent positions are empty.

3. If the conditions are satisfied, we place a flower at the current position and increment the count.

4. Finally, we compare the count with the required number of flowers, and if it’s greater than or equal to the required amount, we return True; otherwise, we return False.

// ES6 Arrow Function
const canPlaceFlowers = (flowerBed, n) => {
    let count = 0;

    for(let i = 0; i < flowerBed.length; i++) {
        if(
            flowerBed[i] === 0 && 
            (i === 0 || flowerBed[i-1] === 0) &&
            (i === flowerBed.length - 1 || flowerBed[i + 1] === 0)
            ) {
                flowerBed[i] = 1;
                count++;
            } 

        if(count >= n) return true;
    }

    return false;

}

Time Complexity: O(N)

Since we Iterate through the entire flowerbed and each element is checked to determine if it’s a valid position. Therefore, the time complexity is linear.

Space Complexity: O(1)

No additional space is used in the solution so the space complexity remains constant.

Approach 2: Optimized Brute Force

In the above approach, there are too many unnecessary checks in the input array. So we can optimize the solution by reducing the number of checks done.

1. Instead of checking every position, we start at the beginning of the flowerbed and move forward by two steps in each iteration.

2. Placing a flower at the current position ensures that the adjacent position cannot have a flower, so we skip the next position.

3. By doing this, we reduce the number of positions we need to check, improving the efficiency of the algorithm.

4. However, the time complexity of this approach is still O(n) since, in the worst case, we may have to visit every position.

/ ES6 Arrow Function
const canPlaceFlowers = (flowerBed, n) => {
    let count = 0, i = 0;

    while(i < flowerBed.length) {
        if(
            flowerBed[i] === 0 &&
            (i === flowerBed.length - 1 || flowerBed[i+1] === 0) &&
            (i === 0 || flowerBed[i - 1] === 0) 
            ) {
                count++;
                i+=2;
            } else {
                i+=1;
            }

        if(count >= n) return true;
    }

    return false;
}

Time Complexity: O(N)

Overall time complexity in this approach remains linear as well. Although, we are reducing the number of checks in the solution still we are iterating throughout the flowerbed.

Space Complexity: O(1)

Since no extra space is used here as well the space complexity remains constant.

Approach 3: Greedy

The greedy approach optimizes the solution further by avoiding unnecessary checks.

1. Similar to the previous approaches, we iterate through the flowerbed.

2. For each position, we check if the current position and its adjacent positions are empty.

3. If they are, we place a flower at the current position, increment the count, and move to the next position.

4. This approach takes advantage of the fact that if we place a flower at a position, it affects the availability of adjacent positions, so we can skip those positions.

5. This optimization reduces the number of iterations in most cases, resulting in improved efficiency.

// ES6 Arrow Function
const canPlaceFlowers = (flowerBed, n) => {
    let count = 0, i = 0;
    while(i < flowerBed.length) {
        if(
            flowerBed[i] === 0 && 
            (i === 0 || flowerBed[i - 1] === 0) && 
            (i === flowerBed.length - 1 || flowerBed[i + 1] === 0)
        ) {
            flowerBed[i] = 1;
            count++;
        }

        i++;

        if(count >= n) return true;
    }

    return false;
}

Time Complexity: O(N)

We are iterating through the entire flowerbed therefore the time taken is linear.

Space Complexity: O(1)

No extra space is used, we only modified the original flowerbed. Therefore, the space complexity is constant.

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 605