🔗 submission url

🧩 Problem: Can Place Flowers

LeetCode link

Description

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted inadjacentplots.Given an integer arrayflowerbedcontaining0's and1's, where0means empty and1means not empty, and an integern, returntrueifnnew flowers can be planted in theflowerbedwithout violating the no-adjacent-flowers rule andfalseotherwise.

Examples

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false

Constraints

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

My Solution

⏱ Runtime: 7 ms
🧠 Memory: 17.9 MB

Code

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

        if n == 0:
            return True

        # Case 1
        if len(flowerbed) == 1:
            return (n == 1 and flowerbed[0] == 0)

        # Case 2
        if flowerbed[0] + flowerbed[1] == 0:
            flowerbed[0] = 1
            n -= 1
            if n <= 0:
                return True

        # Case 3
        if flowerbed[-2] + flowerbed[-1] == 0:
            flowerbed[-1] = 1
            n -= 1
            if n <= 0:
                return True

        # Case 4
        for i in range(1, len(flowerbed) - 1):
            if n <= 0:
                return True
            if flowerbed[i - 1] + flowerbed[i] + flowerbed[i + 1] == 0:
                flowerbed[i] = 1
                n -= 1
        return False

            

        
            

Approach

Noticed that only if there's ... 000 ... or 00 ... or ... 00, I can plant a flower.
I split cases into 1. edge of the pot 2. middle of the pot which become Case2, 3 and 4.
But I realized I didn't consider 1.when length of pot is one 2. n=0, That I added Case 0, 1.

🔁 Feedback

Better Solution

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

Explanation

Same O(N) but, less cases.
If you that spot is empty and previous spot is empty -> plant.
If there was a flower at next spot, remove it.

💬 Review & Thoghts

• I used 'Sliding Window' to solve problem. But faster solutions updated count from the beginning.
• I can understand how faster solution works, but hard to know why they're faster..
• Try lessen the number of if