The O(n) Club: Can Place Flowers—Or How to Not Plant a Bug Farm

The O(n) Club: Can Place Flowers—Or How to Not Plant a Bug Farm

⚡ TL;DR

You’ve got a 0-1 array (flowerbed), a number n, and a simple dream: plant n new flowers, but never let any be next-door neighbors. Just loop left-to-right, greedily filling safe spots and bailing out early if you hit your quota. Java, as always—just as the algorithm gods intended:

// Java: Satisfy your gardening urges, greedily!
int count = 0;
for (int i = 0; i < bed.length; i++) {
    if (bed[i] == 0 && (i == 0 || bed[i-1] == 0) && (i == bed.length-1 || bed[i+1] == 0)) {
        bed[i] = 1;
        count++;
        if (count == n) return true;
    }
}
return count >= n;

🧠 How Devs Usually Mess This Up

Roll-call of classic faceplants:

🔍 What’s Actually Going On

Picture this: You’re a metro traffic czar, squeezing compact cars (flowers) into premier parking spots (flowerbed). The only rule? Cars detest neighbors, so every empty space needs empty sides. Good urban design—or, in array land, a greedy check for each spot. No backtracking, no existential crisis, just left-to-right O(n) efficiency. Boundaries? Imagine both ends as invisible garden gnomes: always helpful, never in the way.

🛠️ PseudoCode

• For each plot (i):
  • If it’s empty (flowerbed[i]==0), check the sides.
• Are neighbors empty?
  • i==0 or left neighbor is 0
  • i==N-1 or right neighbor is 0
• Still good? Plant, set to 1, decrement n. If n==0, you’re done—just return true like a winner.
• The code (Java-style pseudocode):

  for (int i = 0; i < flowerbed.length; i++) {
      if (flowerbed[i] == 0) {
          boolean left = (i == 0) || (flowerbed[i - 1] == 0);
          boolean right = (i == flowerbed.length - 1) || (flowerbed[i + 1] == 0);
          if (left && right) {
              flowerbed[i] = 1;
              n--;
              if (n == 0) return true;
          }
      }
  }
  return n <= 0;

💻 The Code

public boolean canPlaceFlowers(int[] flowerbed, int n) {
    int len = flowerbed.length;
    for (int i = 0; i < len; i++) {
        if (flowerbed[i] == 0) {
            boolean leftOK = (i == 0) || (flowerbed[i - 1] == 0);
            boolean rightOK = (i == len - 1) || (flowerbed[i + 1] == 0);
            if (leftOK && rightOK) {
                flowerbed[i] = 1; // Plant responsibly!
                n--;
                if (n == 0) return true;
            }
        }
    }
    return n <= 0;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Boundary blindness: Skip the first or last plot check—you’ll crash faster than a LIFO stack with no base case.
• Double for loops: You see O(N^2), I see multi-core sadness. Be greedy; be glorious.
• Edge Case Olympics:
  [1,0,0,0,1], n=1 (works!) vs [1,0,0,0,1], n=2 (sorry, even Java can’t fudge this).
• Input preservation: If they want your code to tiptoe, clone the array (Arrays.copyOf()), and complain internally.

Complexity:

• Time: O(N) – one walk through the garden, no detours.
• Space: O(1) – unless your interviewer is a preservationist.

🧠 Interviewer Brain-Tattoo

Greedy is good, but only if you check both sides. Otherwise? Your dreams go out-of-bounds—literally.