Minimum Wait Days to Harvest Flower Bundles
Solve this ProblembloomDay[i] is the day plant i blooms. You want to assemble m bundles, and every bundle needs k adjacent plants in the row that have all already bloomed (each plant can only go into one bundle). Return the earliest day on which all m bundles can be assembled, or -1 if it's never possible.
If m × k exceeds the number of plants, there simply aren't enough plants to ever form m bundles, regardless of how long you wait. Otherwise, waiting longer can only help: every plant bloomed by an earlier day stays bloomed on every later day, so the number of bundles achievable on a given day never decreases as the day advances. That monotonic "more days, never fewer bundles" relationship is exactly what a binary search on the answerBinary Search on the AnswerThe search runs directly over the space of candidate answers — here, every candidate day — rather than over an array. It applies whenever "is this candidate good enough?" only ever gets easier to satisfy as the candidate grows (or only harder, depending on direction). needs: search the range of days directly for the earliest one that already works.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of plants ≤ 10⁵ - ◆
1 ≤ bloomDay[i] ≤ 10⁹ - ◆
1 ≤ m, k ≤ 10⁵
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Day From the Earliest Bloom Onward
BruteIf m bundles are achievable at all, the earliest possible day is somewhere between the first plant to bloom and the last. Try every day in that range, in order: for each candidate day, scan the row once, counting a bundle every time k consecutive plants have all bloomed by that day (resetting the streak the moment a plant hasn't bloomed yet). The first day whose bundle count reaches m is the answer. Correct, but re-scanning the whole row for every single candidate day wastes a lot of work once the bloom days spread out.
O(n · maxDay)O(1)1class Solution {
2 public int minHarvestDay(int[] bloomDay, int m, int k) {
3 int n = bloomDay.length;
4 if ((long) m * k > n) return -1;
5 int lo = bloomDay[0], hi = bloomDay[0];
6 for (int b : bloomDay) { lo = Math.min(lo, b); hi = Math.max(hi, b); }
7 for (int day = lo; day <= hi; day++) {
8 if (canMakeBundles(bloomDay, m, k, day)) return day;
9 }
10 return -1;
11 }
12
13 private boolean canMakeBundles(int[] bloomDay, int m, int k, int day) {
14 int bundles = 0, run = 0;
15 for (int b : bloomDay) {
16 if (b <= day) {
17 run++;
18 if (run == k) { bundles++; run = 0; }
19 } else {
20 run = 0;
21 }
22 }
23 return bundles >= m;
24 }
25}Optimal — Binary Search on the Day
OptimalWaiting longer never reduces how many bundles are possible — every plant that had bloomed by an earlier day is still bloomed on any later day, so the achievable bundle count only grows (or stays the same) as the day advances. That monotonic relationship lets binary search find the earliest feasible day directly: whenever a candidate day already yields at least m bundles, remember it and try an earlier day; otherwise the day is too early, so search later.
O(n · log(maxDay - minDay))O(1)1class Solution {
2 public int minHarvestDay(int[] bloomDay, int m, int k) {
3 int n = bloomDay.length;
4 if ((long) m * k > n) return -1;
5 int lo = bloomDay[0], hi = bloomDay[0];
6 for (int b : bloomDay) { lo = Math.min(lo, b); hi = Math.max(hi, b); }
7 int ans = -1;
8 while (lo <= hi) {
9 int mid = lo + (hi - lo) / 2;
10 if (canMakeBundles(bloomDay, m, k, mid)) {
11 ans = mid;
12 hi = mid - 1;
13 } else {
14 lo = mid + 1;
15 }
16 }
17 return ans;
18 }
19
20 private boolean canMakeBundles(int[] bloomDay, int m, int k, int day) {
21 int bundles = 0, run = 0;
22 for (int b : bloomDay) {
23 if (b <= day) {
24 run++;
25 if (run == k) { bundles++; run = 0; }
26 } else {
27 run = 0;
28 }
29 }
30 return bundles >= m;
31 }
32}