[LeetCode] 60. Can Place Flowers

 

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.

 

My answer is terrible

 

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:

        for i in range(0, len(flowerbed)):
            if not flowerbed[i]:
                if i==0 and len(flowerbed) > 1 and not flowerbed[i+1]:
                    flowerbed[i]=1
                    n = n-1
                elif i==len(flowerbed)-1 and not flowerbed[i-1]:
                    flowerbed[i]=1
                    n = n-1
                elif not i==len(flowerbed)-1 and not flowerbed[i+1] and not flowerbed[i-1]:
                    flowerbed[i]=1
                    n = n-1

        if n > 0:
            return False
        else:
            return True

 

 

 

 

Improved

 

 

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        length = len(flowerbed)
        i=0
        
        while i < length:
            if n==0:
                return True
            
            if flowerbed[i] == 0:
                left_empty = (i==0) or (flowerbed[i-1] == 0)
                right_empty = (i==length - 1) or (flowerbed[i+1]==0)

                if left_empty and right_empty:
                    flowerbed[i] = 1
                    n-=1
                    i+=2
                    continue
            
            i+=1

        return n == 0

 

 

Both solutions solve the same problem : determining whether n flowers can be placed in a flowerbed without violating the rule that no two flowers can be adjacent.

 

Iteration Strategy:

- First : Iterages through the entire flowerbed using a for loop.

The index increments by 1 in every iteration, regardless of whether a flower is placed or not.

- Second : Uses a while loop. If a flower is placed, it skips the next index by incrementing i by 2, reducing redundant checks.

 

Efficiency:

- First : Always checks all elements in the flowerbed, even after placing a flower. 

This can lead to unnecessary computations, especially in cases where n flowers have already been placed before reaching the end.

- Second : Optimizes by skipping checks for adjacent positions when a flower is placed. This avoids redundant checks and improves efficiency.

 

Condition for Termination :

Returns early if n reaches 0 within the loop. Otherwise, it checks whether n==0 after iterating through the entire flowerbed.

 

Final Return Value :

Returns n==0 after the loop, ensuring the exact number of flowers required were placed.