Practice/Amazon/Leetcode 1482. Minimum Number of Days to Make m Bouquets

Leetcode 1482. Minimum Number of Days to Make m Bouquets

CodingMust

Problem

You have a garden with flowers arranged in a straight line. Each flower will bloom on a specific day, given in the array bloomDay, where bloomDay[i] represents the day when the flower at position i will bloom.

You need to create m bouquets, and each bouquet must contain exactly k adjacent flowers that have already bloomed. Your task is to find the minimum number of days you need to wait before you can make all m bouquets.

If it's impossible to make m bouquets (for example, if you don't have enough flowers in total), return -1.

Requirements

1. Return the minimum day number when m bouquets can be formed
2. Each bouquet requires exactly k adjacent flowers (consecutive positions in the garden)
3. A flower can only be used in one bouquet
4. If creating m bouquets is impossible, return -1
5. Flowers must have bloomed (day ≤= current day) to be usable

Constraints

• 1 ≤= bloomDay.length ≤= 100,000
• 1 ≤= bloomDay[i] ≤= 1,000,000,000
• 1 ≤= m ≤= 1,000,000
• 1 ≤= k ≤= bloomDay.length
• Time complexity should be better than O(n * max(bloomDay))
• Space complexity should be O(1) excluding the input

Examples

Example 1:

Input: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1 Output: 3 Explanation: On day 3, flowers at positions 0 (bloomed day 1), 2 (bloomed day 3), and 4 (bloomed day 2) have all bloomed. Since k=1, each single flower can form a bouquet, so we can make 3 bouquets.

Example 2:

` Input: bloomDay = [1, 10, 3, 10, 2], m = 2, k = 2 Output: 10 Explanation: We need 2 bouquets with 2 adjacent flowers each (4 flowers total).

• Day 1: Only position 0 bloomed
• Day 2: Positions 0, 4 bloomed (not adjacent)
• Day 3: Positions 0, 2, 4 bloomed (no pair of adjacent flowers)
• Day 10: All flowers bloomed, positions 0-1 and 2-3 can form 2 bouquets `

Example 3:

Input: bloomDay = [7, 7, 7, 7], m = 2, k = 3 Output: -1 Explanation: We need 2 * 3 = 6 flowers but only have 4 flowers total.