Can Place Flowers - Leetcode 605 - Python

0:00 - Read the problem
1:37 - Drawing Explanation
6:27 - Coding Explanation

leetcode 605

#google #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[premrr]

This was a tricky one!
Instead of adding 0s in beginning and the end, We can just use a ternary statement like:
*prev = i == 0 ? 0 : flowerbed[i-1];*
*next = i == len(flowerbed)-1 ? 0 : flowerbed[i+1]*

And if both are 0, we can place 1.

[jeffpeng]

the same logic of the first solution can be applied without using auxillary space
class Solution:
def canPlaceFlowers(self, f: List[int], n: int) -> bool:
for i in range(len(f)):
leftOk = i == 0 or f[i-1] == 0
rightOk = i == len(f) -1 or f[i+1] == 0
if leftOk and f[i] == 0 and rightOk:
f[i] = 1
n -= 1
return n <= 0

[imaaduddin]

Thank you so much for these videos man! So glad I found your channel as I’m in the interview prep process!

[Tony-wyyp]

The trick to add [0] and [0] at the beginning and the end is smart!

[JoseMejia-tpod]

Whether we start with a 0 or 1 we can assume that the before the begging there is a 0 just like you mentioned but there is no need to add it. If there was a 0 before us and we are currently at a 1, then you move 2 spaces, but if you were at a 0 but the one in front of you is a 1, then move 3 spaces. because of these movements you are out of the way of the previous limits, so you dont have to check behind you, only forward, and finally if you reach a case that doesnt satisfy either then you can plant.

var canPlaceFlowers = function(flowerbed, n) {
let current = 0

while (current < flowerbed.length && n > 0) {
if (flowerbed[current] === 1) {
current += 2
continue
} else if (flowerbed[current] === 0 && flowerbed[current + 1] === 1) {
current += 3
continue
} else {
n--
current += 2
}
}

return n > 0 ? false : true
};

[ZM-rump]

Was stuck on the final edge case for a good while. Adding the 0's makes so much sense!

[hck]

Leetcode's editorial solution is imo simpler and more intuitive.

[sergiobost]

Love your vids, here is an alternate solution I just did: 
95.55% speed, 62.24% space

class Solution:
def canPlaceFlowers(self, flowerbed, n):
pointer = 0
while pointer < len(flowerbed):
if flowerbed[pointer] == 1: # We have a flower already planted
pointer += 2 # Skip 2
else:
if pointer < len(flowerbed) - 1: # Make sure we dont go out of bounds with check on our next line
if flowerbed[pointer + 1]: # Make sure the next spot does not contain a flower
pointer += 1
continue
n -= 1
pointer += 2
return n <= 0

[venkatasundararaman]

We can take a greedy approach and store where the lastone appeared. This can be either the 1 we place or the 1 which comes from the input array. The solution is as follows
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
lastPlaced = -1

for i in range(len(flowerbed)):
if flowerbed[i] == 0:
if lastPlaced >= 0 and i - lastPlaced < 2:
continue
lastPlaced = i
n -= 1
else:
if lastPlaced >= 0 and i - lastPlaced < 2:
n += 1
lastPlaced = i
return n <= 0

[AustinWeeks]

Not sure why but this one was actually really intuitive/easy for me! Could be just because of some JavaScript magic when checking an index out of bounds though:

function canPlaceFlowers(flowerbed, n) {
for (let i = 0; i < flowerbed.length; i++) {
if ((flowerbed[i - 1] || 0) !== 0) continue;
if (flowerbed[i] !== 0) continue;
if ((flowerbed[i + 1] || 0) !== 0) continue;
flowerbed[i] = 1;
n--;
}
return n <= 0;
};

[kapilIT]

In alternate solution, we can always initialize "empty" with 1 which will avoid special handling (i.e. round towards zero) and improve the time.

[muntadher]

Thank you, my code ran -8 ms than yours!!

class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
F = [0]+flowerbed+[0]
ones = 0
for i in range(1, len(F)-1):
if ones== n: return True
if 1 in F[i-1:i+2]: continue
ones +=1
F[i]=1
return False if ones!=n else True

[luckyim]

This is very very ticky :( I spent like 20 minutes to drill it and got depressed! thank so much for your solution!

[animeshsingh]

Just handle the edge in the if block instead of random math.

if n == 0:
return True
for i in range(len(flowerbed)):
if flowerbed[i] == 0 and (i == 0 or flowerbed[i-1] == 0) and (i == len(flowerbed)- 1 or flowerbed[i+1] == 0):
flowerbed[i] = 1
n -= 1
if n == 0:
return True
return False

[Moch]

This problem had some crazy annoying edge cases.

If you want to avoid O(n) space, just modify the original array (or keep a prev/next vals)

Otherwise, I used O(n) space with a temp array just like you. Makes the problem much easier

[linonator]

What if, starting from the beginning of the list we only checked the current and current index + 2… I say that because we know no flowers can be planted next to each other so that should be the case in the array already.

So we check flower[0] and right is 0 if that’s 0 we plant but if its 1 we move 2 positions (since no adjacent flowers are allowed anyway)

[darko]

This is brilliant. Appreciate the solution.

[ManojKumar-]

Hmm.. I was trying to use decimal values for 3 digits binary.. Got fed up solving that way. Thanks for explaining.

[gillupenn]

Very smart suggestion of add 0 at the edges, for java lovers heres corresponding java code:
```class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {

int sum = 0;
int last = flowerbed.length - 1;

// just one item
if (n == 0) {
return true;
}
if (last == 0) {
if (flowerbed[0] == 0) {
return true;
} else {
return false;
}
}

int[] newArr = new int[flowerbed.length + 2];
for (int i=0; i<flowerbed.length; i++) {
newArr[i+1] = flowerbed[i];
}

// general case for the middle
for (int i=1; i<newArr.length - 1; i++) {
if (newArr[i - 1] == 0 && newArr[i] == 0 && newArr[i+1] == 0) {
sum++;
newArr[i] = 1;
}
}

return n <= sum;

}
}
```

[DeKeL_BaYaZi]

this is not a great solution tbh. why adding 0 to both edges of the list?




class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
places = 0
for i, f in enumerate(flowerbed):
prev = flowerbed[i - 1] if i - 1 >= 0 else 0
next = flowerbed[i + 1] if i + 1 < len(flowerbed) else 0
if f == 0 and next == 0 and prev == 0:
places += 1
return places >= n