Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0605 - Can Place Flowers
    0605 - Can Place Flowers
    0605 - Can Place Flowers
    0605 - Can Place Flowers

    0605 - Can Place Flowers

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/can-place-flowers/

    Solution 1 - Greedy Scan

    Iterate through the flowerbed from left to right. At each position, check if the current plot is empty and both adjacent plots are also empty (treating out-of-bounds as empty). If so, plant a flower there and decrement n. Return True once n reaches zero.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - Counting Consecutive Zeros

    Instead of modifying the array, count consecutive empty plots between flowers (or boundaries). For each group of k consecutive zeros, (k - 1) // 2 flowers can be planted. Sum up the count and compare with n.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 0605.1 - Can Place Flowers - Solution 1 - Greedy Scan """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        """Can Place Flowers Function"""
        for i in range(len(flowerbed)):
            if flowerbed[i] == 0:
                left_empty = (i == 0) or (flowerbed[i - 1] == 0)
                right_empty = (i == len(flowerbed) - 1) or (flowerbed[i + 1] == 0)
                if left_empty and right_empty:
                    flowerbed[i] = 1
                    n -= 1
                    if n <= 0:
                        return True
        return n <= 0


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().canPlaceFlowers([1, 0, 0, 0, 1], 1))  # True
    print(Solution().canPlaceFlowers([1, 0, 0, 0, 1], 2))  # False
    print(Solution().canPlaceFlowers([0, 0, 1, 0, 0], 2))  # True
    print(Solution().canPlaceFlowers([1], 0))               # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0605.2 - Can Place Flowers - Solution 2 - Counting Consecutive Zeros """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        """Can Place Flowers Function"""
        count = 0
        zeros = 1  # treat left boundary as an implicit zero

        for plot in flowerbed:
            if plot == 0:
                zeros += 1
            else:
                count += (zeros - 1) // 2
                zeros = 0

        zeros += 1  # treat right boundary as an implicit zero
        count += (zeros - 1) // 2

        return count >= n


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().canPlaceFlowers([1, 0, 0, 0, 1], 1))  # True
    print(Solution().canPlaceFlowers([1, 0, 0, 0, 1], 2))  # False
    print(Solution().canPlaceFlowers([0, 0, 1, 0, 0], 2))  # True
    print(Solution().canPlaceFlowers([1], 0))               # True
    print(Solution().canPlaceFlowers([0], 1))               # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()