algoadvance

Leetcode 605. Can Place Flowers

Problem Statement

You have a long flowerbed in which some 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

Clarifying Questions

1. Can the flowerbed array be empty?
   • No, according to the problem statement, it’s always provided as non-empty.
2. What should be the output if n is 0?
   • The output should be true since we don’t need to plant any flowers.
3. What constraints are placed on the values in the flowerbed array?
   • The flowerbed array will only contain 0’s and 1’s.

Strategy

1. Iterate Through the Flowerbed:
   • Iterate through each position in the flowerbed.
2. Check Planting Conditions:
   • For each element, check if the current plot is 0 and its adjacent plots (left and right) are also 0 or out of bounds of the array.
3. Plant a Flower if Possible:
   • If the position meets the criteria, plant a flower there (set the position to 1) and decrease the count of n.
4. Check Completion:
   • If at any point n reaches 0, return true.
5. Return the Result:
   • After completing the loop, if n is still greater than 0, return false.

Code

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

Time Complexity

• Time Complexity: O(N), where N is the number of elements in the flowerbed array. This is because we iterate through the flowerbed array once.
• Space Complexity: O(1), as we are not using any extra space that grows with the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?