Short Python


  • 1

    In order to place x flowers between position i and position j, we must have j - i >= 2*x + 2. And remember to handle to boundary cases.

    class Solution(object):
        def canPlaceFlowers(self, flowerbed, n):
            """
            :type flowerbed: List[int]
            :type n: int
            :rtype: bool
            """
            have = [-2] + [i for i, x in enumerate(flowerbed) if x] + [len(flowerbed) + 1]
            return sum(abs(have[i] - have[i-1] - 2) // 2 for i in range(1, len(have))) >= n
    

  • 0

    Fails for example flowerbed = [1,1,0,0], n = 1. (fixed now)


  • 0

    @StefanPochmann
    Ugh, I really should be more careful next time. Thanks for point it out, fixed it by adding abs. Kinda lazy to write a longer one.


  • 0

    I assume the sum(...) is supposed to be the number of flowers you can place? If so, then the not n or should be unnecessary, no? That's btw how I found the original flaw, because it didn't get accepted when I removed the not n or.


  • 0

    @StefanPochmann
    You totally got the point! Actually I wrote the version without abs during the contest and oops, it fails for the case [1,1,1,1,1], n == 0. I had to commit I didn't really think it through at that time and added not n in a hurry.


  • 1

    Just shortening it a bit further:

    def canPlaceFlowers(self, flowerbed, n):
        have = [i for i, x in enumerate([1, 0] + flowerbed + [0, 1]) if x]
        return sum(abs(b - a - 2) // 2 for a, b in zip(have, have[1:])) >= n

  • 0

    Similar idea using regex, but much slower:

        def canPlaceFlowers(self, flowerbed, n):
            slots = re.findall(r'0+', '0'+''.join(map(str, flowerbed))+'0')
            return sum((len(slot)-1)/2 for slot in slots) >= n
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.