605. Can Place Flowers (Array, Greedy)

링크 - https://leetcode.com/problems/can-place-flowers/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

이 문제는 왼쪽에서 오른쪽으로 가면서 꽃이 있는지 확인하고 집어넣는 문제이다.

Code

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

        return count >= n

Complexity

Time Complexity: O(n)

Space Complexity: O(1)