Logo

Kode$word

LeetCode 1482: Minimum Number of Days to Make m Bouquets – Binary Search on the Earliest Day
LeetCode 1482: Minimum Number of Days to Make m Bouquets – Binary Search on the Earliest Day

LeetCode 1482: Minimum Number of Days to Make m Bouquets – Binary Search on the Earliest Day

A Complete Guide to Solving the Bouquet Problem Using Binary Search on Answer with Intuition, Dry Run, and Java Implementation

18 views
0
0
Binary SearchArraysBinary Search on AnswerLeetCodeMedium
Github icon

Try the Problem

You can practice the problem here:

https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/


Problem Description

You are given an integer array bloomDay, where:

bloomDay[i]

represents the day on which the i-th flower blooms.

You are also given two integers:

m → number of bouquets required
k → number of adjacent flowers needed for one bouquet

Rules

To create one bouquet, you must use:

k adjacent flowers

Important constraints:

  1. A flower can only be used once.
  2. Only flowers that have already bloomed can be used.
  3. Flowers must be adjacent in the array.

Your goal is to determine the minimum number of days required so that it becomes possible to create m bouquets.

If it is impossible, return:

-1


Example Walkthrough

Example 1

Input

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

Output

3

Explanation

We need:

3 bouquets
1 flower each

Garden progress:

Day 1

[x, _, _, _, _]

Bouquets possible = 1

Day 2

[x, _, _, _, x]

Bouquets possible = 2

Day 3

[x, _, x, _, x]

Bouquets possible = 3 ✅

Minimum day = 3

Example 2

Input

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

Output

-1

Explanation:

We need:

3 bouquets × 2 flowers = 6 flowers

But we only have:

5 flowers

So it is impossible.

Example 3

Input

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

Output

12

Explanation:

Day 7

[x,x,x,x,_,x,x]

Only 1 bouquet can be made.

Day 12

[x,x,x,x,x,x,x]

Now 2 bouquets can be formed.

Minimum day = 12


Constraints

1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n

Important observations:

  1. bloomDay[i] can be very large
  2. The array size can be 100,000
  3. A brute force simulation for every day would be too slow


Thinking About the Problem

At first glance, the problem may look like a simulation problem, where we check the garden day by day.

However, this approach quickly becomes inefficient because the maximum bloom day can be as large as:

10^9

So instead of checking every day sequentially, we need to search intelligently for the minimum valid day.


Key Observation

If we wait for more days, more flowers will bloom.

Which means:

Days ↑ → Flowers available ↑ → Bouquets possible ↑

This means the function is monotonic.

If it is possible to make m bouquets on day X, then it will also be possible on any day after X.

This type of pattern strongly suggests using:


Binary Search on Answer

Approach: Binary Search on Minimum Day

Instead of checking every day, we search between:

minimum bloom day → maximum bloom day

For each candidate day mid:

  1. Assume we wait until day mid.
  2. Count how many bouquets we can make.
  3. If we can make at least m bouquets, try smaller days.
  4. Otherwise, increase the day.


How We Count Bouquets

While scanning the garden:

  1. If the flower has bloomed (bloomDay[i] <= mid)
  2. → increase adjacent flower count
  3. If a flower has not bloomed yet
  4. → reset the adjacent counter

Whenever we have:

k adjacent flowers

we form one bouquet.


Your Java Implementation (Binary Search + Greedy Counting)

class Solution {

// Function to check if we can make m bouquets
// if we wait until 'mid' days
public boolean binaryS(int mid, int[] arr, int m, int k){

int flower = 0;
int bouq = 0;

for(int i = 0; i < arr.length; i++){

// Flower has bloomed
if(arr[i] <= mid){
flower++;
}
else{

// Calculate bouquets from collected flowers
bouq += flower / k;

// Reset adjacent counter
flower = 0;
}
}

// Handle remaining flowers after loop
bouq += flower / k;

return bouq >= m;
}


public int minDays(int[] bloomDay, int m, int k) {

// If required flowers exceed total flowers
if((long)m * k > bloomDay.length)
return -1;

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

// Find search range
for(int a : bloomDay){
min = Math.min(min, a);
max = Math.max(max, a);
}

int ans = -1;

// Binary Search
while(min <= max){

int mid = min + (max - min) / 2;

if(binaryS(mid, bloomDay, m, k)){

ans = mid;

// Try smaller day
max = mid - 1;
}
else{

// Need more days
min = mid + 1;
}
}

return ans;
}
}


Dry Run Example

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

Search range:

1 → 10

Binary search steps:

mid = 5
Possible bouquets = 3 → valid

Try smaller:

mid = 2
Bouquets = 2 → not enough

Increase day:

mid = 3
Bouquets = 3 → valid

Minimum day:

3


Time Complexity

Binary search runs:

O(log(maxDay - minDay))

For each check we scan the array:

O(n)

Total complexity:

O(n log(10^9))

Which is efficient for n = 10^5.

Space Complexity

O(1)

No extra space is required.


Key Takeaway

This problem is a classic example of:

Binary Search on Answer

Whenever a problem asks:

Find the minimum value such that a condition becomes true

Binary search is often the best solution.


Conclusion

The Minimum Number of Days to Make m Bouquets problem teaches an important interview technique: transforming a simulation problem into a search problem.

By recognizing the monotonic nature of the problem, we can apply binary search on the answer space and efficiently determine the minimum day required to create the desired number of bouquets.

Mastering problems like this will significantly improve your understanding of binary search patterns, which are extremely common in coding interviews.

Related Articles

LeetCode 875: Koko Eating Bananas – Find the Minimum Eating Speed Using Binary Search

LeetCode 875: Koko Eating Bananas – Find the Minimum Eating Speed Using Binary Search

Step-by-Step Explanation of the Koko Eating Bananas Problem with Intuition, Dry Run, and Java Implementation

Read Article
LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

A Complete Guide to Solving “Find Unique Binary String” Using Hashing, Brute Force Thinking, and Cantor’s Diagonalization

Read Article
LeetCode 1283 — Find the Smallest Divisor Given a Threshold | Binary Search on Answer Explained

LeetCode 1283 — Find the Smallest Divisor Given a Threshold | Binary Search on Answer Explained

Another clean example of the "Binary Search on Answer" pattern — intuition, greedy check, commented Java code, dry run, and complexity analysis.

Read Article
Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Understand how to convert a binary string into an alternating pattern with the minimum number of flips using a simple greedy approach.

Read Article

Ai Assistant Kas