[leetcode #605] Can Place Flowers

Problem

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.

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 * 10⁴
・ flowerbed[i] is 0 or 1.
・ There are no two adjacent flowers in flowerbed.
・ 0 <= n <= flowerbed.length

Idea

화단에 꽃을 심는데, 인접하게 꽃을 심지 않을 경우 주어진 n개의 꽃을 심을 수 있는지 확인하는 문제다.

Brute-force로 풀어도 풀리는 문제라 쉽다.

주어진 화단을 탐색하면서 현재 장소와 양옆에 꽃이 없을 경우 꽃을 심은 뒤 n을 1씩 감소시키면 된다.

탐색이 끝난 뒤 n이 0보다 작거나 같으면 모든 꽃을 심었으므로 true를 리턴하면 된다.

Solution

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

        return n <= 0;
    }
}

Reference

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