Algorithm
LeetCode 75
Can Place Flowers

605. Can Place Flowers

Tags

  • Array
  • Greedy

Link

https://leetcode.com/problems/can-place-flowers/description/?envType=study-plan-v2&envId=leetcode-75 (opens in a new tab)

Question

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

Answer

JavaScript

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function (flowerbed, n) {
  for (let i = 0; i < flowerbed.length; i++) {
    if (
      flowerbed[i] !== 1 &&
      flowerbed[i - 1] !== 1 &&
      flowerbed[i + 1] !== 1
    ) {
      n--;
      i++;
    }
  }
  return n <= 0;
};
/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function (flowerbed, n) {
  let count = 0;
  let pre = -1;
  let next = 1;
 
  for (let i = 0; i < flowerbed.length; i++, pre++, next++) {
    const preValue = getValue(flowerbed, pre);
    const currentValue = getValue(flowerbed, i);
    const nextValue = getValue(flowerbed, next);
 
    if (preValue + currentValue + nextValue == 0) {
      flowerbed[i] = 1;
      count++;
    }
 
    // if (
    //   getValue(flowerbed, pre) +
    //     getValue(flowerbed, i) +
    //     getValue(flowerbed, next) ==
    //   0
    // ) {
    //   flowerbed[i] = 1;
    //   count++;
    // }
  }
 
  return count >= n;
};
 
var getValue = function (flowerbed, i) {
  if (i < 0 || i >= flowerbed.length) {
    return 0;
  }
  return flowerbed[i];
};
/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function (flowerbed, n) {
  for (let i = 0; i < flowerbed.length; i++) {
    const left = i === 0 || flowerbed[i - 1] === 0;
    const right = i === flowerbed.length - 1 || flowerbed[i + 1] === 0;
 
    if (left && right && flowerbed[i] === 0) {
      flowerbed[i] = 1;
      n--;
    }
  }
 
  return n <= 0;
};
/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function (flowerbed, n) {
  let numOfPossiblePot = 0;
 
  let pointer = 0;
 
  if (flowerbed.length == 0) {
    return false;
  }
  if (n == 0) {
    return true;
  }
 
  if (flowerbed.length == 1) {
    if (n == 1 && flowerbed[0] == 0) {
      return true;
    }
    if (n == 0) {
      return true;
    }
    return false;
  }
 
  if (flowerbed[0] == 0 && flowerbed[1] == 0) {
    numOfPossiblePot++;
    flowerbed[0] = 1;
  }
 
  if (
    flowerbed[flowerbed.length - 1] == 0 &&
    flowerbed[flowerbed.length - 2] == 0
  ) {
    numOfPossiblePot++;
    flowerbed[flowerbed.length - 1] = 1;
  }
 
  for (i = 1; i < flowerbed.length - 1; i++) {
    if (flowerbed[i] == 0 && flowerbed[i + 1] == 0 && flowerbed[i - 1] == 0) {
      numOfPossiblePot++;
      flowerbed[i] = 1;
      i++;
    }
  }
 
  return n <= numOfPossiblePot;
};
To Be or Not to BeContainer with Most Water