We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Can Place Flowers

Number: 605

Difficulty: Easy

Paid? No

Companies: LinkedIn, Meta, Google, Amazon, Microsoft, Bloomberg, Apple, Atlassian, Adobe, Uber, Oracle, Yandex, SOTI

Problem Description

Given an array representing a flowerbed where 0 means an empty plot and 1 means a plot with a flower, determine if it is possible to plant n new flowers without violating the rule that no two flowers can be adjacent.

Key Insights

  • Use a greedy approach by scanning the array once.
  • For each position, check if the current plot and its adjacent plots (taking care of edge conditions) are empty.
  • If the position is suitable, plant a flower there (simulate by setting it to 1) and skip the next plot.
  • Count the number of new flowers planted and compare it with n.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the flowerbed array. Space Complexity: O(1), as the solution uses only a constant amount of extra space.

Solution

The solution iterates through the flowerbed array and checks for available spots to plant a flower. A spot is available if:

  • The current plot is empty.
  • If it’s not the first plot, the left neighbor is empty.
  • If it’s not the last plot, the right neighbor is empty.

Once a valid spot is found:

  • Plant a flower by setting the value to 1.
  • Increment the count of planted flowers.
  • Increment the index by one extra step to skip the adjacent plot (to ensure no adjacent flowers are planted).

If the number of planted flowers meets or exceeds n during the iteration, return true immediately. Otherwise, after the loop, check whether the count is at least n.

Code Solutions

def canPlaceFlowers(flowerbed, n):
    count = 0  # Count the number of planted flowers
    i = 0
    while i < len(flowerbed):
        # Check if current plot is empty and its neighbors (or boundaries) are empty
        if (flowerbed[i] == 0 and
            (i == 0 or flowerbed[i - 1] == 0) and
            (i == len(flowerbed) - 1 or flowerbed[i + 1] == 0)):
            flowerbed[i] = 1  # Plant a flower here
            count += 1      # Increment count
            if count >= n:  # Return early if we have planted enough flowers
                return True
            i += 1  # Skip next plot to maintain the no-adjacent rule
        i += 1
    return count >= n

# Example usage:
print(canPlaceFlowers([1,0,0,0,1], 1))  # Expected output: True
print(canPlaceFlowers([1,0,0,0,1], 2))  # Expected output: False
← Back to All Questions