605. Can Place Flowers

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 if n new flowers can be planted in the flowerbed

 Examples:

Input: flowerbed = [1,0,0,0,1], n = 1 Output: true
Input: flowerbed = [1,0,0,0,1], n = 2 Output: false

Note: Didn't handle n = 0 case. Made a mistake in i ==L-1 case, wrote i < L-1

def canPlaceFlowers(flowerbed: List[int], n: int):
       
    i = 0
    placed = 0
    L = len(flowerbed)
   
    while i < L and placed < n:
        if  (not i or not flowerbed[i-1]) \
            and \
            not flowerbed[i] \
            and \
            (i == L-1 or not flowerbed[i+1]):
           
            flowerbed[i] = 1
            placed += 1                            
        i += 1
       
    return placed >= n

Comments

Post a Comment

Popular posts from this blog

Longest Increasing Subsequence

Problem Given an integer array  nums , return the length of the longest strictly increasing subsequence. Solution DP. Second solution can be O(nlg(n)) First solution : Two for loops checking for each number, what would be the max subsequence based on 1 to n-1. Second solution : Build a sequence, whose i-th position stores the best option (number) for subsequences of length i . Use binary search to make the search log(n) The second approach does not build a single subsequence does produce the correct length. # First: DP, O(N 2 ) from typing import List def lengthOfLIS ( self , nums : List [ int ]) -> int :     local_sol = [ 1 ]*( len ( nums ))     global_sol = 1     for i in range ( 1 , len ( nums )):         for j in range ( i ):             if nums [ i ] > nums [ j ]:                 local_sol [ i ] = max ( local_sol [ i ], local_sol [ j ]+ 1 )...
Read more

K-th smallest in BST

  Problem Given the  root  of a binary search tree, and an integer  k , return  the   k th   smallest value ( 1-indexed ) of all the values of the nodes in the tree . Solution In-order traversal. Recursive or Iterative. Recursive is easy but need to traverse entire tree Or add a lot of ugly code. Iterative is tricky. Two while loops. One always slides to the left. The root is like a pointer.  It does not always come from the stack! # Iterative def kthSmallest ( self , root : Optional [ TreeNode ], k : int ) -> int :         stack = []         while True :             while root :                 stack . append ( root )                 root = root .left             root = stack . pop ()             k -= 1         ...
Read more

Minimum Arrows to Burst Balloons

Image
   Problem Given a set of balloons (start, end), find number of arrows needed to burst. An arrow bursts all the balloons in its vertical path. Solution Greedy. Trick is to sort them by 'end'. Keep a current end that for the current row.  Every time, a balloon starts after the current end Increase the arrow count.  # Greedy def findMinArrowShots ( self , points : List [ List [ int ]]) -> int :                   if not points :             return 0                 points . sort ( key = lambda x : x [ 1 ])             cur_end = points [ 0 ][ 1 ]         arrow = 1                 for start , end in points :             if start > cur_end :                 arrow += 1     ...
Read more