605. Can Place Flowers

Description

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

My Solution

 
/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
  let cnt = 0;
  // if there is only one plot and it is empty and n is 1
  if(flowerbed.length == 1 && flowerbed[0] === 0 && n === 1) {
      return true
  }
 
  for(let i = 0; i < flowerbed.length; i++) {
    // if the first plot is empty and the next plot is empty
    if(i === 0 && flowerbed[i] === 0 && flowerbed[i+1] === 0) {
        flowerbed[i] = 1;
        cnt++;
    // if the plot is empty and the previous plot is empty and the next plot is empty
    } else if (flowerbed[i] === 0 && flowerbed[i-1] === 0 && flowerbed[i+1] === 0) {
        flowerbed[i] = 1;
        cnt++
    // if the last plot is empty and the previous plot is empty
    } else if (i === flowerbed.length -1 && flowerbed[i] === 0 && flowerbed[i-1] === 0) {
        flowerbed[i] = 1;
        cnt++
    }
  }
  // if the count of new flowers is greater than or equal to n
  return cnt >= n;
};
 

Solution from others

 
// The solution is similar to mine, but it is more concise and efficient.
var canPlaceFlowers = function(flowerbed, n) {
  let count = 0;
  for(let i = 0; i < flowerbed.length; i++) {
      if(flowerbed[i] === 0 && (i === 0 || flowerbed[i-1] === 0) 
        && (i === flowerbed.length - 1 || flowerbed[i+1] === 0)) {
          flowerbed[i] = 1;
          count++;
      }
  }
  return count >= n;
};
 

Explanation

1. Start Counting: Begin with a count of 0. This will track how many flowers we can plant.
2. Loop Through: Go through each spot in the flowerbed one by one.
3. Check Conditions: For each spot, check three things:

• If the current spot is empty (0 means no flower there).
• If the spot to the left is empty or it's the first spot in the flowerbed.
• If the spot to the right is empty or it's the last spot in the flowerbed.

4. Plant Flower: If all conditions are met (the spot is empty and both adjacent spots are empty or edges), plant a flower there (change 0 to 1) and increase your count by 1.
5. Repeat: Keep doing this for every spot in the flowerbed.
6. Final Check: In the end, see if the count of flowers you planted is equal to or more than 'n', the number of flowers you wanted to plant.
7. Result: Return true if you could plant at least 'n' flowers without breaking the rules; otherwise, return false.

Note

In JavaScript, negative index is not allowed. It will return undefined. If you want to check the last element of an array, you can use array[array.length - 1] instead of array[-1].