algoadvance

Leetcode 605. Can Place Flowers

Problem Statement

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

Clarifying Questions

  1. Are the values in the flowerbed array only 0’s and 1’s?
    • Yes, the array contains only 0’s and 1’s.
  2. Is the flowerbed array fixed in size or can it be variable?
    • The size of the flowerbed array can vary.
  3. Is it possible for n to be larger than the length of the flowerbed?
    • Yes, but in that case, we can immediately return false because we can’t plant more flowers than available plots.

Strategy

To solve this problem, we’ll iterate through the flowerbed array and look for potential spots where a new flower can be planted while adhering to the no-adjacent-flowers rule. We’ll follow these steps:

  1. Traverse the flowerbed array.
  2. Check if the current plot and its adjacent plots (previous and next) are empty.
  3. If a flower can be planted at the current plot, update the array and increment the count of planted flowers.
  4. If the number of flowers planted matches or exceeds n, return true.
  5. If the end of the array is reached and the number of flowers planted is still less than n, return false.

Code

#include <vector>

bool canPlaceFlowers(std::vector<int>& flowerbed, int n) {
    int count = 0;
    int len = flowerbed.size();
    
    for (int i = 0; i < len; ++i) {
        if (flowerbed[i] == 0) {
            // Check if the previous and next positions are 0 or out of bounds
            bool emptyPrev = (i == 0 || flowerbed[i-1] == 0);
            bool emptyNext = (i == len - 1 || flowerbed[i+1] == 0);
            
            if (emptyPrev && emptyNext) {
                // Plant the flower here
                flowerbed[i] = 1;
                count++;
                
                // Check if we have planted enough flowers
                if (count >= n) {
                    return true;
                }
            }
        }
    }
    
    return count >= n;
}

Time Complexity

The time complexity of the solution is (O(N)), where (N) is the length of the flowerbed array. This is because we are making a single pass through the array to check possible planting spots and update the flowerbed.

Explanation

  1. Iteration: We iterate over the flowerbed array checking each plot.
  2. Conditions Check: For each empty plot (flowerbed[i] == 0), we check if the previous (i-1) and next (i+1) plots are also empty or out of bounds.
  3. Planting: If both adjacent plots are empty, we plant a flower by setting flowerbed[i] = 1 and increase the count of planted flowers.
  4. Early Exit: If at any point the count of planted flowers reaches or exceeds n, we return true quickly. If the loop ends and the count is still less than n, we return false, as it’s not possible to plant the required number of flowers.

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