LeetCode 1482 - Minimum Number of Days to Make m Bouquets

This problem asks us to determine the minimum number of days required to make a given number of bouquets from a garden o

leetcodemediumarraybinary-search

LeetCode Problem 1482

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

This problem asks us to determine the minimum number of days required to make a given number of bouquets from a garden of flowers that bloom on different days. We are provided an array bloomDay, where bloomDay[i] indicates the day the i-th flower blooms. A bouquet consists of exactly k adjacent flowers, and we need to make exactly m bouquets. The output is the minimum day at which it becomes possible to create all m bouquets. If there are not enough flowers to meet the requirements (m * k > n), we return -1.

The problem essentially combines two constraints: adjacency of flowers for a bouquet and individual bloom days. We must carefully track which flowers are available on any given day and ensure they can form the necessary bouquets. Constraints show that the array size can be up to 10^5 and bloom days can be very large (10^9), so a naive solution that checks day by day would be inefficient. Key edge cases include situations where m * k > n (impossible case), k = 1 (simplest adjacency requirement), or all flowers bloom on the same day.

Approaches

The brute-force approach involves iterating day by day, checking which flowers have bloomed, and counting how many bouquets can be made each day. This guarantees correctness but is too slow because bloom days can reach 10^9 and array size 10^5. Iterating through potentially billions of days is infeasible.

The optimal approach leverages binary search on the answer. We know the minimum day must lie between the earliest bloom and the latest bloom. For any candidate day, we can efficiently check if it is possible to form m bouquets by counting contiguous blocks of flowers that have bloomed. By adjusting the search range based on feasibility, we converge on the minimum day efficiently. This is a standard "decision problem" technique where a monotonic property (more days always allows at least as many bouquets) allows binary search.

Approach Time Complexity Space Complexity Notes
Brute Force O(D * n), D = max(bloomDay) O(1) Check every day if bouquets can be formed, very slow for large max bloomDay
Optimal O(n log(max(bloomDay))) O(1) Binary search over days, check feasibility with linear scan each time

Algorithm Walkthrough

  1. Initial Checks: If m * k > n, return -1 immediately because there are not enough flowers to form the required bouquets.
  2. Binary Search Setup: Define left as the minimum bloom day and right as the maximum bloom day.
  3. Feasibility Check: Write a helper function canMake(day) that returns True if we can form at least m bouquets by the given day. Scan the bloomDay array, count consecutive bloomed flowers, and whenever k consecutive flowers are found, increment the bouquet count and reset the consecutive counter.
  4. Binary Search Execution: While left < right, check the middle day mid = (left + right) // 2. If canMake(mid) is true, set right = mid to find a smaller feasible day. Otherwise, set left = mid + 1.
  5. Return Result: After binary search, left will hold the minimum day to make m bouquets. Return left.

Why it works: The binary search works because the function canMake(day) is monotonic. If it is possible to make bouquets on day d, it will also be possible for any day > d. This guarantees that the first feasible day found by binary search is indeed the minimum.

Python Solution

from typing import List

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if m * k > n:
            return -1
        
        def canMake(day: int) -> bool:
            bouquets = 0
            consecutive = 0
            for bloom in bloomDay:
                if bloom <= day:
                    consecutive += 1
                    if consecutive == k:
                        bouquets += 1
                        consecutive = 0
                else:
                    consecutive = 0
            return bouquets >= m
        
        left, right = min(bloomDay), max(bloomDay)
        while left < right:
            mid = (left + right) // 2
            if canMake(mid):
                right = mid
            else:
                left = mid + 1
        return left

Explanation: We first check if the number of flowers is sufficient. The canMake function performs a single pass through bloomDay to count possible bouquets, resetting consecutive flowers whenever a flower is not bloomed by the candidate day. Binary search then finds the minimum feasible day efficiently.

Go Solution

func minDays(bloomDay []int, m int, k int) int {
    n := len(bloomDay)
    if m*k > n {
        return -1
    }

    minDay, maxDay := bloomDay[0], bloomDay[0]
    for _, day := range bloomDay {
        if day < minDay {
            minDay = day
        }
        if day > maxDay {
            maxDay = day
        }
    }

    canMake := func(day int) bool {
        bouquets, consecutive := 0, 0
        for _, bloom := range bloomDay {
            if bloom <= day {
                consecutive++
                if consecutive == k {
                    bouquets++
                    consecutive = 0
                }
            } else {
                consecutive = 0
            }
        }
        return bouquets >= m
    }

    left, right := minDay, maxDay
    for left < right {
        mid := (left + right) / 2
        if canMake(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

Go Notes: We explicitly calculate minDay and maxDay because Go lacks a built-in min or max for slices. The canMake function and binary search logic are identical to Python. Handling slices and integer division carefully avoids off-by-one errors.

Worked Examples

Example 1: bloomDay = [1,10,3,10,2], m = 3, k = 1

Binary search range: left=1, right=10. Check midpoints and feasibility:

Day Can make bouquets? Comment
5 Yes Flowers <= 5: [1, _, 3, _, 2], can make 3 bouquets
3 Yes Flowers <= 3: [1, _, 3, _, 2], can make 3 bouquets
2 No Flowers <= 2: [1, _, _, _, 2], can make 2 bouquets

Minimum day found is 3.

Example 2: bloomDay = [1,10,3,10,2], m = 3, k = 2

Number of flowers required = 3 * 2 = 6, total flowers = 5 → return -1 immediately.

Example 3: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3

Binary search finds day 12 as the minimum to get 2 bouquets of 3 adjacent flowers.

Complexity Analysis

Measure Complexity Explanation
Time O(n log(max(bloomDay))) Binary search over possible days, with a linear scan each time to count bouquets
Space O(1) Only counters and binary search variables are used, no additional structures needed

The binary search range is limited by the min and max bloom days, and each feasibility check is a single linear scan. No extra space proportional to input size is required.

Test Cases

# Basic examples
assert Solution().minDays([1,10,3,10,2], 3, 1) == 3  # example 1
assert Solution().minDays([1,10,3,10,2], 3, 2) == -1  # example 2
assert Solution().minDays([7,7,7,7,12,7,7], 2, 3) == 12  # example 3

# Edge cases
assert Solution().minDays([1], 1, 1) == 1  # single flower
assert Solution().minDays([1,2,3], 1, 3) == 3  # need all flowers for one bouquet
assert Solution().minDays([1,2,3], 2, 2) == -1  # not enough flowers
assert Solution().minDays([5,5,5,5,5], 1, 5) == 5  # all same day, single bouquet
assert Solution().minDays([1,1000000000], 1, 1) == 1  # large max bloom day
Test Why
Basic examples Validate correctness for examples provided
Single flower Tests minimum input size
All flowers needed Ensure adjacency counted correctly