Can Place Flowers

Leetcode Daily Challenge (20th March, 2023)

20 March, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

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 if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Link: https://leetcode.com/problems/can-place-flowers/

Problem Explanation with examples:-

Example 1

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true
Explanation: You can place one flower in the middle of the row to have a flowered garden.

Example 2

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false
Explanation: There is no way to place two flowers in the middle of a row with only one empty slot.

Constraints

1 <= flowerbed.length <= 2 * 104
flowerbed[i] is 0 or 1.
There are no two adjacent flowers in flowerbed.
0 <= n <= flowerbed.length

Intuition:-

Somehow, we need to make the array an alternating sequence of 0 and 1.
If we can make the array an alternating sequence of 0 and 1, then we can place flowers and return True if n is exhausted.
Simply iterating through the array and placing flowers at 0s will not work because we need to make sure that the 1s are not adjacent to each other.
If we iterate through the whole array based on our constraint and exhaust n, then we can return True.

Solution:-

Initially check if n is 0, if so, return True.
Iterate through the array from 0 to len(flowerbed)-2.
If the current element is 1, then we can skip the next element because we cannot place a flower there.
If the current element is 0, then we have two cases.
If the current element is the first element and the next element is 0, then we can place a flower there.
If the current element is not the first element and the previous element and the next element are 0, then we can place a flower there.
In either of the above cases, we can place a flower there and decrement n by 1.
If n is exhausted, then we can return True.
After the loop, we need to check if n is not yet exhausted and the last element is 0 and the second last element is 0, then we can place a flower there and decrement n by 1.
Finally, we can return n==0.

Code:-

JAVA Solution

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (n == 0) {
            return true;
        }
        for (int i = 0; i < flowerbed.length - 1; i++) {
            if (flowerbed[i] == 1) {
                i += 1;
            } else {
                if ((i == 0 && flowerbed[i+1] == 0) || (flowerbed[i-1] == 0 && flowerbed[i+1] == 0)) {
                    flowerbed[i] = 1;
                    n -= 1;
                    if (n == 0) {
                        return true;
                    }
                }
            }
        }
        if (n > 0 && flowerbed[flowerbed.length-1] == 0 && flowerbed[flowerbed.length-2] == 0) {
            flowerbed[flowerbed.length-1] = 1;
            n -= 1;
        }
        return n == 0;
    }
}

Python Solution

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        if n == 0:
            return True
        for i in range(len(flowerbed)-1):
            if flowerbed[i] == 1:
                i += 2
            else:
                if (i == 0 and flowerbed[i+1] == 0) or (flowerbed[i-1] == 0 and flowerbed[i+1] == 0):
                    flowerbed[i] = 1
                    n -= 1
                    if n == 0:
                        return True

        if n > 0 and flowerbed[len(flowerbed)-1] == 0 and flowerbed[len(flowerbed)-2] == 0:
            flowerbed[len(flowerbed)-1] = 1
            n -= 1
        return n==0

Complexity Analysis:-

TIME:-

Time complexity is O(n), where n is the length of the input flowerbed array. We iterate over the entire array once, checking each element to see if a flower can be planted in that spot.

SPACE:-

Space complexity is O(1) since we only use a constant amount of extra space to store variables like the loop index and the count of remaining flowers to plant. We modify the input flowerbed array in place, so no extra space is required for a copy of the array.