Minimum Number of Days to Make m Bouquets LeetCode solution in Python

1
class Solution:
2

3
    def minDays(
4
        self,
5
        listOfFlowerBloomDays: List[int],
6
        targetNumberOfBouquets: int,
7
        flowersPerBouquet: int,
8
    ) -> int:
9

10
        def numberOfBouquetsWeCanMakeOnThisDay(dayThatWeAreChecking):
11

12
            currentListOfAdjacentBloomedFlowers = []
13
            numberOfBouquetsWeCanMakeOnThisDay = 0
14

15
            for dayThatFlowerBlooms in listOfFlowerBloomDays:
16

17
                # check if the flower has bloomed on this day
18
                if dayThatFlowerBlooms <= dayThatWeAreChecking:
19

20
                    # add to the list an adjacent bloomed flowers, I use 'x' because the description uses an 'x'
21
                    currentListOfAdjacentBloomedFlowers.append("x")
22

23
                else:
24
                    # we've hit a day where we don't have a bloomed flower, so the list of adjacent bloomed flowers has to be reset
25
                    # BUT FIRST figure out how many bouquets we can make with this list of adjacent bloomed flowers
26
                    numberOfBouquetsWeCanMakeOnThisDay += (
27
                        len(currentListOfAdjacentBloomedFlowers) // flowersPerBouquet
28
                    )
29

30
                    # RESET list of adjacent bloomed flowers cause we're on a day where the a flower has not bloomed yet
31
                    currentListOfAdjacentBloomedFlowers = []
32

33
            # we've gone through the entire listOfFlowerBloomDays list and need to check if the "residual" current list
34
            # of adjacent bloomed flowers can make a bouquet ... so handle it here
35
            numberOfBouquetsWeCanMakeOnThisDay += (
36
                len(currentListOfAdjacentBloomedFlowers) // flowersPerBouquet
37
            )
38

39
            return numberOfBouquetsWeCanMakeOnThisDay
40

41
        # if the TOTAL amount of flowers we need doesn't match the number of possible flowers we can grow,
42
        # then the given inputs are impossible for making enough bouquets (we don't have enough flowers)
43
        totalNumberOfFlowersNeeded = targetNumberOfBouquets * flowersPerBouquet
44
        numberOfFlowersWeCanGrow = len(listOfFlowerBloomDays)
45
        if numberOfFlowersWeCanGrow < totalNumberOfFlowersNeeded:
46
            return -1
47

48
        # no need to go past the day of the flower with the longest bloom date
49
        leftDay = 0
50
        rightDay = max(listOfFlowerBloomDays)
51

52
        while leftDay < rightDay:
53

54
            # currentDay is functioning as the "mid" of a binary search
55
            currentDay = leftDay + (rightDay - leftDay) // 2
56

57
            # as in most binary searches, we check if the mid (which I'm calling 'currentDay') satisfies the constraint
58
            # that is, if we can make the target amount of bouquets on this day
59
            if numberOfBouquetsWeCanMakeOnThisDay(currentDay) < targetNumberOfBouquets:
60

61
                # womp womp, we can't make enough bouquets on this day, so set up for next iteration
62
                # the "correct day" is on the right side, so we get rid of all the "incorrect days" on the left side
63
                # by updating the left to the currentDay+1
64
                leftDay = currentDay + 1
65
            else:
66

67
                # yay, we can make enough bouquets on this day, but we don't know if this is the "minimum day"
68
                # we discard the right side to keep searching
69
                rightDay = currentDay
70

71
        # leftDay >= rightDay, so we've found the "minimum day"
72
        return leftDay