Jobs

Interviews

Discussions

Can Place Flowers

Easy

Apple

1 view

Topics:

ArraysGreedy Algorithms

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 true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

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

Can Place Flowers

Easy

Apple

1 view

Topics:

ArraysGreedy Algorithms

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.

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible size of the `flowerbed` array?
Can `n` be zero or negative?
Is the `flowerbed` guaranteed to contain only 0s and 1s, or could there be other values?
If it's not possible to plant `n` flowers, should I return `false` immediately, or should I try to plant as many as possible and then return `false`?
Is there a minimum size of the `flowerbed` array?

Brute Force Solution

Approach

The brute force strategy involves checking every single possible location in the garden to see if we can plant a flower. We'll try planting a flower in each available spot, one by one, and see if it works.

Here's how the algorithm would work step-by-step:

Look at the first empty spot in the garden.
Check if you can plant a flower there without violating the rule about not planting flowers in adjacent plots. This means checking the spots to the left and right.
If you can plant a flower, put one there temporarily and reduce the number of flowers you still need to plant.
Now, look at the next empty spot and repeat the checking process.
If you cannot plant in that location, move to the next empty spot.
Keep going until you've either planted all the flowers you needed to plant or you've checked every single spot in the garden.
If you planted all the flowers, the answer is yes. Otherwise, the answer is no.

Code Implementation

def can_place_flowers_brute_force(flowerbed, number_of_flowers_to_plant):
    garden_length = len(flowerbed)
    flowers_planted = 0

    for i in range(garden_length):
        # Check if the current spot is empty
        if flowerbed[i] == 0:
            can_plant = True

            # Check left adjacent spot
            if i > 0 and flowerbed[i - 1] == 1:
                can_plant = False

            # Check right adjacent spot
            if i < garden_length - 1 and flowerbed[i + 1] == 1:
                can_plant = False

            if can_plant:
                # Plant a flower if possible
                flowerbed[i] = 1

                #Reduce the amount of flowers to plant
                flowers_planted += 1

                if flowers_planted >= number_of_flowers_to_plant:
                    return True

    return flowers_planted >= number_of_flowers_to_plant

Big(O) Analysis

Time Complexity

O(n) – The provided brute force approach iterates through each plot in the flowerbed array of size n at most once. For each plot, it performs a constant-time check to see if a flower can be planted. Therefore, the algorithm visits each plot a single time resulting in a linear time complexity.

Space Complexity

O(1) – The provided brute force algorithm iterates through the input flowerbed array, but it does not create any auxiliary data structures that scale with the input size N (where N is the length of the flowerbed). It may temporarily modify the flowerbed in place, but this doesn't count towards auxiliary space. The algorithm only uses a few constant-size variables to keep track of the current position and the number of flowers planted. Therefore, the space complexity is constant.

Optimal Solution

Approach

The goal is to plant as many flowers as possible in designated spots, but flowers can't be planted in adjacent spots. The optimal strategy involves checking each spot and planting a flower only if it's possible without violating the adjacency rule.

Here's how the algorithm would work step-by-step:

Look at each planting spot one by one.
Check if the current spot is empty.
If the spot is empty, check the spots immediately to the left and right of it to see if they also are empty or out of range.
If the current spot, and both spots to its left and right are empty (or beyond the edge), then plant a flower in the current spot.
After potentially planting a flower, reduce the number of flowers we still need to plant.
Continue this process until you run out of spots to check or you have planted all the flowers you needed to plant.
Finally, check if the amount of flowers planted is equal to the amount required. If so, then it is possible to plant them and if not, then it isn't.

Code Implementation

def canPlaceFlowers(flowerbed, number_of_flowers): 
    number_of_plots = len(flowerbed)
    flowers_planted = 0

    for i in range(number_of_plots):
        # Check if current spot is empty
        if flowerbed[i] == 0:
            empty_left_plot = (i == 0) or (flowerbed[i - 1] == 0)
            empty_right_plot = (i == number_of_plots - 1) or (flowerbed[i + 1] == 0)

            # If left and right spots are empty, plant a flower
            if empty_left_plot and empty_right_plot:
                flowerbed[i] = 1

                # Increment planted flowers count.
                flowers_planted += 1

                if flowers_planted >= number_of_flowers:
                    return True

    # Check if planted flowers equals required flowers
    return flowers_planted >= number_of_flowers

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each planting spot in the input array once. For each spot, it performs a constant amount of work: checking if the spot is empty and then checking its immediate left and right neighbors. Therefore, the runtime is directly proportional to the number of spots, n, in the input array, resulting in O(n) time complexity.

Space Complexity

O(1) – The provided solution iterates through the input array but does not create any auxiliary data structures that scale with the input size N (where N is the length of the flowerbed). It only uses a few constant-sized variables to keep track of the current position and the number of flowers planted. Therefore, the auxiliary space required remains constant regardless of the input size, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
flowerbed is null or empty	If flowerbed is null or empty, return true if n is 0, otherwise return false.
flowerbed has length 1	If the flowerbed has length 1, check if the single plot is 0, if so increment planted flowers, and return if planted flowers >= n.
n is 0	If n is 0, we can always plant 0 flowers, so return true.
flowerbed contains only 1s	If the flowerbed contains only 1s, we cannot plant any flowers, so return false if n > 0.
flowerbed contains only 0s	If the flowerbed contains only 0s, we can plant (length + 1) / 2 flowers (integer division).
n is greater than the maximum possible number of plantable flowers	The algorithm should correctly identify when it's impossible to plant enough flowers and return false.
flowerbed starts and/or ends with 0s	The algorithm should correctly handle planting flowers at the beginning and end of the array.
Large flowerbed size	The solution should scale linearly with the size of the flowerbed to avoid time limit exceeded errors.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible size of the `flowerbed` array?
Can `n` be zero or negative?
Is the `flowerbed` guaranteed to contain only 0s and 1s, or could there be other values?
If it's not possible to plant `n` flowers, should I return `false` immediately, or should I try to plant as many as possible and then return `false`?
Is there a minimum size of the `flowerbed` array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Look at the first empty spot in the garden.
Check if you can plant a flower there without violating the rule about not planting flowers in adjacent plots. This means checking the spots to the left and right.
If you can plant a flower, put one there temporarily and reduce the number of flowers you still need to plant.
Now, look at the next empty spot and repeat the checking process.
If you cannot plant in that location, move to the next empty spot.
Keep going until you've either planted all the flowers you needed to plant or you've checked every single spot in the garden.
If you planted all the flowers, the answer is yes. Otherwise, the answer is no.

Code Implementation

def can_place_flowers_brute_force(flowerbed, number_of_flowers_to_plant):
    garden_length = len(flowerbed)
    flowers_planted = 0

    for i in range(garden_length):
        # Check if the current spot is empty
        if flowerbed[i] == 0:
            can_plant = True

            # Check left adjacent spot
            if i > 0 and flowerbed[i - 1] == 1:
                can_plant = False

            # Check right adjacent spot
            if i < garden_length - 1 and flowerbed[i + 1] == 1:
                can_plant = False

            if can_plant:
                # Plant a flower if possible
                flowerbed[i] = 1

                #Reduce the amount of flowers to plant
                flowers_planted += 1

                if flowers_planted >= number_of_flowers_to_plant:
                    return True

    return flowers_planted >= number_of_flowers_to_plant

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Look at each planting spot one by one.
Check if the current spot is empty.
If the spot is empty, check the spots immediately to the left and right of it to see if they also are empty or out of range.
If the current spot, and both spots to its left and right are empty (or beyond the edge), then plant a flower in the current spot.
After potentially planting a flower, reduce the number of flowers we still need to plant.
Continue this process until you run out of spots to check or you have planted all the flowers you needed to plant.
Finally, check if the amount of flowers planted is equal to the amount required. If so, then it is possible to plant them and if not, then it isn't.

Code Implementation

def canPlaceFlowers(flowerbed, number_of_flowers): 
    number_of_plots = len(flowerbed)
    flowers_planted = 0

    for i in range(number_of_plots):
        # Check if current spot is empty
        if flowerbed[i] == 0:
            empty_left_plot = (i == 0) or (flowerbed[i - 1] == 0)
            empty_right_plot = (i == number_of_plots - 1) or (flowerbed[i + 1] == 0)

            # If left and right spots are empty, plant a flower
            if empty_left_plot and empty_right_plot:
                flowerbed[i] = 1

                # Increment planted flowers count.
                flowers_planted += 1

                if flowers_planted >= number_of_flowers:
                    return True

    # Check if planted flowers equals required flowers
    return flowers_planted >= number_of_flowers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
flowerbed is null or empty	If flowerbed is null or empty, return true if n is 0, otherwise return false.
flowerbed has length 1	If the flowerbed has length 1, check if the single plot is 0, if so increment planted flowers, and return if planted flowers >= n.
n is 0	If n is 0, we can always plant 0 flowers, so return true.
flowerbed contains only 1s	If the flowerbed contains only 1s, we cannot plant any flowers, so return false if n > 0.
flowerbed contains only 0s	If the flowerbed contains only 0s, we can plant (length + 1) / 2 flowers (integer division).
n is greater than the maximum possible number of plantable flowers	The algorithm should correctly identify when it's impossible to plant enough flowers and return false.
flowerbed starts and/or ends with 0s	The algorithm should correctly handle planting flowers at the beginning and end of the array.
Large flowerbed size	The solution should scale linearly with the size of the flowerbed to avoid time limit exceeded errors.