Suppose 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 - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

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



Note:

The input array won't violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won't exceed the input array size.

Source: leetcode | Difficulty: EASY
Tags: Data structures

Greedy algorithms

Starter code: class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        

Solutions:
class Solution:

	def canPlaceFlowers(self, flowerbed, n):
		p = flowerbed.count(1)
		m = int(len(flowerbed) / 2)
		if p + n <= m + 1:
			pos = 0
			while pos < len(flowerbed):
				if n == 0:
					print(n)
					return True
				elif pos + 1 < len(flowerbed):
					if flowerbed[pos] == 0 and flowerbed[pos + 1] == 0:
						print(pos)
						n -= 1
						pos += 2
					elif flowerbed[pos] == 1:
						pos += 2
					else:
						pos += 3
				elif flowerbed[pos] == 0:
					n -= 1
					pos += 2
			if n == 0:
				return True
			else:
				return False
		else:
			return False


class Solution:

	def canPlaceFlowers(self, flowerbed, n):
		possible = 0
		repeated = 1
		for f in flowerbed:
			if f:
				if repeated:
					possible += (repeated - 1) // 2
				repeated = 0
			else:
				repeated += 1
		if repeated:
			possible += repeated // 2
		return possible >= n


class Solution:

	def canPlaceFlowers(self, flowerbed, n):
		cnt = 0
		for i in range(len(flowerbed)):
			if flowerbed[i] == 0:
				if (i == 0 or flowerbed[i - 1] == 0) and (i == len(flowerbed) - 1 or flowerbed[i + 1] == 0):
					flowerbed[i] = 1
					cnt += 1
		return cnt >= n


class Solution:

	def canPlaceFlowers(self, flowerbed, n):
		if n == 0:
			return True
		L = len(flowerbed)
		if n > (L + 1) // 2:
			return False
		if L == 1:
			return flowerbed[0] == 0
		(cnt, i) = (0, 0)
		while i < L:
			if flowerbed[i] == 1:
				i += 2
			elif i < L - 1 and flowerbed[i + 1] == 1:
				i += 3
			elif i == L - 1:
				cnt += int(flowerbed[i - 1] == 0)
				i += 1
			elif i == 0 or flowerbed[i - 1] == 0:
				cnt += 1
				i += 2
		return cnt >= n


class Solution:

	def canPlaceFlowers(self, nums, n):
		count = 0
		nums = [0] + nums + [0]
		for i in range(1, len(nums) - 1):
			if nums[i] == 0:
				if nums[i + 1] == 0 and nums[i - 1] == 0:
					count += 1
					nums[i] = 1
		if count >= n:
			return True
		else:
			return False


class Solution:

	def canPlaceFlowers(self, flowerbed, n):
		lenFb = len(flowerbed)
		for i in range(lenFb):
			if i == 0:
				if flowerbed[i] == 0:
					if i == lenFb - 1:
						flowerbed[i] = 1
						n -= 1
					elif flowerbed[i + 1] == 0:
						flowerbed[i] = 1
						n -= 1
			elif i == lenFb - 1:
				if flowerbed[i] == 0:
					if flowerbed[i - 1] == 0:
						flowerbed[i] = 1
						n -= 1
			elif flowerbed[i - 1] == 0 and flowerbed[i + 1] == 0 and (flowerbed[i] == 0):
				flowerbed[i] = 1
				n -= 1
		return not n > 0


class Solution:

	def canPlaceFlowers(self, flowerbed, n):
		canPlant = 0
		if len(flowerbed) == 1:
			if flowerbed[0] == 0:
				canPlant += 1
				flowerbed[0] = 1
		else:
			for i in range(len(flowerbed)):
				if flowerbed[i] == 0:
					if i == 0:
						if flowerbed[i + 1] == 0:
							flowerbed[i] = 1
							canPlant += 1
					elif i == len(flowerbed) - 1:
						if flowerbed[i - 1] == 0:
							flowerbed[i] = 1
							canPlant += 1
					elif flowerbed[i + 1] == 0 and flowerbed[i - 1] == 0:
						flowerbed[i] = 1
						canPlant += 1
		if canPlant >= n:
			return True
		else:
			return False


class Solution:

	def canPlaceFlowers(self, flowerbed, n):
		(count, pos) = (0, 0)
		while pos < len(flowerbed):
			if (pos - 1 < 0 or not flowerbed[pos - 1]) and (not flowerbed[pos]) and (pos + 1 > len(flowerbed) - 1 or not flowerbed[pos + 1]):
				print(pos)
				count += 1
				pos += 2
			else:
				pos += 1
		return count >= n


class Solution:

	def canPlaceFlowers(self, flowerbed, n):
		result = False
		if n == 0:
			return True
		if flowerbed:
			if len(flowerbed) == 1:
				if flowerbed[0] == 0:
					flowerbed[0] = 1
					n -= 1
					return n == 0
			for i in range(len(flowerbed)):
				(left, right) = (False, False)
				if flowerbed[i] == 0 and n != 0:
					if i == 0 and len(flowerbed) >= 2:
						if flowerbed[i] == 0 and flowerbed[i + 1] == 0:
							flowerbed[i] = 1
							n -= 1
					else:
						left = i - 1 >= 0 and flowerbed[i - 1] == 0
					if i == len(flowerbed) - 1 and len(flowerbed) >= 2:
						if flowerbed[i] == 0 and flowerbed[i - 1] == 0:
							flowerbed[i] = 1
							n -= 1
					else:
						right = i + 1 < len(flowerbed) and flowerbed[i + 1] == 0
					if left and right:
						flowerbed[i] = 1
						n -= 1
			result = n == 0
		return result


class Solution:

	def canPlaceFlowers(self, flowerbed, n):
		if n == 0:
			return True
		temp = 0
		m = 0
		if flowerbed[0] == 0:
			temp = 1
		for (i, plot) in enumerate(flowerbed):
			if plot == 0:
				temp += 1
				if i == len(flowerbed) - 1:
					temp += 1
			if plot == 1 or i == len(flowerbed) - 1:
				m += int((temp - 1) / 2)
				temp = 0
			if m >= n:
				return True
		return False