Can Place Flowers - Practice Coding Problems

Can Place Flowers - Problem

Array Greedy Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: flowerbed = [1,0,0,0,1], n = 1

› Output: true

💡 Note: We can plant 1 flower at position 2. Position 1 is invalid (adjacent to flower at 0), position 3 is invalid (adjacent to flower at 4), but position 2 has empty neighbors on both sides.

Example 2 — Not Enough Space

$ Input: flowerbed = [1,0,0,0,1], n = 2

› Output: false

💡 Note: We can only plant 1 flower at position 2. There's no second valid position that doesn't violate the adjacency rule, so we cannot plant 2 flowers.

Example 3 — Edge Case All Empty

$ Input: flowerbed = [0,0,0], n = 2

› Output: true

💡 Note: We can plant flowers at positions 0 and 2. Position 1 cannot be used because it would be adjacent to both planted flowers.

Constraints

1 ≤ flowerbed.length ≤ 2 × 10⁴
flowerbed[i] is 0 or 1
There are no two adjacent flowers in flowerbed
0 ≤ n ≤ flowerbed.length

Visualization

Tap to expand

Understanding the Visualization

Input

Flowerbed array with 0s (empty) and 1s (planted), plus number n

Process

Find valid empty positions where both neighbors are empty

Output

Return true if we can place n flowers, false otherwise

Key Takeaway

🎯 Key Insight: Use greedy approach - plant whenever you find a valid spot, as early placement never blocks optimal solutions

Asked in

G Google 15 a Amazon 12 in LinkedIn 8

The key insight is to use a greedy approach - plant flowers whenever we find a valid empty spot. The greedy strategy works because planting earlier never prevents optimal future placements. Best approach achieves O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Plant Whenever Possible	O(n)	O(1)	Scan left to right and plant a flower whenever we find a valid empty spot
Brute Force - Try All Combinations	O(C(m,n) × n)	O(n)	Generate all possible ways to place n flowers and check if any is valid

Greedy - Plant Whenever Possible — Algorithm Steps

Step 1: Iterate through each position in the flowerbed
Step 2: For each empty position, check if it's safe to plant
Step 3: A position is safe if both neighbors are empty (or don't exist)
Step 4: Plant flower and increment count, return true if we reach n

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Left to Right

Check each position sequentially

Check Validity

Ensure no adjacent flowers exist

Plant Greedily

Place flower immediately when valid

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* flowerbed, int size, int n) {
    if (n == 0) return true;
    
    int count = 0;
    
    for (int i = 0; i < size; i++) {
        if (flowerbed[i] == 0) {
            // Check if we can plant here
            bool leftEmpty = (i == 0) || (flowerbed[i-1] == 0);
            bool rightEmpty = (i == size-1) || (flowerbed[i+1] == 0);
            
            if (leftEmpty && rightEmpty) {
                flowerbed[i] = 1;  // Plant flower
                count++;
                if (count >= n) {
                    return true;
                }
            }
        }
    }
    
    return count >= n;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int flowerbed[1000];
    int size = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        flowerbed[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    int n = atoi(line);
    
    bool result = solution(flowerbed, size, n);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the flowerbed array of length n

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

34.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Plant Whenever Possible — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler