Minimum Days to Make $M$ Bouquets | Binary Search (BS-13)

1. Problem Statement Overview

You are given an array of integers bloomDay where bloomDay[i] represents the day the $i$-th flower blooms. You are also given two integers $M$ (the number of bouquets you need to make) and $K$ (the number of adjacent flowers required to make a single bouquet). Your objective is to find the minimum number of days you need to wait so that you can make at least $M$ bouquets. If it is impossible to make $M$ bouquets regardless of how long you wait, return -1.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Blooming Garden & Workers

Imagine you manage a botanical garden where flowers bloom at different scheduled days. You receive an urgent order for $M$ floral arrangements (bouquets), and each arrangement strictly requires $K$ adjacent flowers from your garden bed.

• If you check too early (e.g., Day 3), only a few scattered flowers have bloomed; you cannot form adjacent groups of size $K$.
• As days pass (Day 7, Day 11, Day 12...), more flowers bloom, creating contiguous blocks of bloomed flowers.
• Once you reach a certain threshold day (e.g., Day 12), you finally have enough valid adjacent clusters to tie your required $M$ bouquets. Waiting beyond that day (e.g., Day 13) still works, but the problem demands the minimum possible day.

3. The Impossible Case (Edge Case Analysis)

Before designing any algorithmic search, we must identify when the task is fundamentally impossible.

• Total Flowers Needed: To create $M$ bouquets of size $K$, you need a total of $M \times K$ flowers.
• Total Available Flowers: Let $N$ be the total number of flowers in the bloomDay array (i.e., $N = \text{bloomDay.length}$).
• The Impossible Rule: If the total flowers required exceed the total flowers available in the garden ($M \times K > N$), it is mathematically impossible to form the bouquets even if all flowers are fully bloomed. In this scenario, immediately return -1.

// Check for impossible case
if ((long) m * k > bloomDay.length) {
    return -1;
}

Note: We cast m * k to long to prevent potential integer overflow issues in competitive programming and production environments.

4. Establishing the Search Space (min and max Days)

To find the minimum number of days using Binary Search, we first need to define our search bounds (low and high):

• low (Minimum Possible Day): The earliest day any single flower can bloom is the minimum value present in the bloomDay array. Waiting any fewer days than this minimum will result in zero bloomed flowers.
• high (Maximum Possible Day): The latest day any flower blooms is the maximum value present in the bloomDay array. On this day, 100% of the flowers in the garden are guaranteed to be bloomed.

Thus, our search space is:

5. Designing the Feasibility Function (isPossible)

We need a helper function that answers the core question:

"Can we form at least $M$ bouquets of size $K$ if we wait for $d$ days?"

Walkthrough of the Feasibility Logic

1. Iterate through the bloomDay array from index $0$ to $N-1$.
2. Maintain a running consecutive counter of bloomed flowers:
   • If bloomDay[i] <= d, the flower has bloomed by day $d$. Increment consecutive++.
   • If bloomDay[i] > d, the flower has not bloomed by day $d$. This breaks our contiguous chain. We calculate how many bouquets could be formed from the accumulated consecutive flowers (consecutive / K), add it to our total bouquets count, and reset consecutive = 0.
3. End-of-Day Check: When the loop finishes, any remaining consecutive flowers at the end of the array must also be converted into bouquets (bouquets += consecutive / K).
4. Compare total bouquets formed against $M$:
   • If bouquets >= M, return true (it is feasible on day $d$).
   • Else, return false.

Feasibility Function Implementation

private boolean isPossible(int[] bloomDay, int day, int m, int k) {
    int bouquets = 0;
    int consecutive = 0;

    for (int i = 0; i < bloomDay.length; i++) {
        if (bloomDay[i] <= day) {
            consecutive++;
        } else {
            bouquets += (consecutive / k);
            consecutive = 0;
        }
    }
    // Add remaining consecutive flowers at the end of the array
    bouquets += (consecutive / k);

    return bouquets >= m;
}

6. Naive Brute Force Approach vs. Optimized Binary Search

Approach 1: Linear Brute Force

• Strategy: Iterate through every single day sequentially from low (min) to high (max). For each day, invoke isPossible(). The first day that returns true is our minimum answer.
• Time Complexity: $\mathcal{O}((\text{max} - \text{min} + 1) \times N)$, where $N$ is the number of flowers. If the day range is large (e.g., $1$ to $1,000,000$), this approach results in a Time Limit Exceeded (TLE) error.

Approach 2: Optimized Binary Search

• Strategy: Because the feasibility property is monotonic (if day $d$ is possible, any day $> d$ is also possible; if day $d$ is impossible, any day $< d$ is also impossible), we can apply Binary Search on Answers.
• Execution Flow:
  Structure & Concept Flow

  Copy DiagramCopy

  Low (Min Day) ------ Mid Day ------ High (Max Day)

  | | |

  Infeasible Test `mid` Feasible

   
  • Compute mid = low + (high - low) / 2.
  • Test if isPossible(bloomDay, mid, M, K) is true.
  • If true, record mid as a potential answer and search the left half (high = mid - 1) to find an even smaller valid day.
  • If false, search the right half (low = mid + 1) because we need more time for flowers to bloom.

7. Complete Code Implementation (Java)

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        long totalFlowersNeeded = (long) m * k;
        if (totalFlowersNeeded > bloomDay.length) {
            return -1; // Impossible case
        }

        int low = Integer.MAX_VALUE;
        int high = Integer.MIN_VALUE;

        // Find min and max days in bloomDay array
        for (int day : bloomDay) {
            low = Math.min(low, day);
            high = Math.max(high, day);
        }

        int ans = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (isPossible(bloomDay, mid, m, k)) {
                ans = mid;          // Record valid day
                high = mid - 1;     // Try to find a smaller valid day on the left
            } else {
                low = mid + 1;      // Need more days, search on the right
            }
        }

        return ans;
    }

    private boolean isPossible(int[] bloomDay, int day, int m, int k) {
        int bouquets = 0;
        int consecutive = 0;

        for (int i = 0; i < bloomDay.length; i++) {
            if (bloomDay[i] <= day) {
                consecutive++;
            } else {
                bouquets += (consecutive / k);
                consecutive = 0;
            }
        }
        bouquets += (consecutive / k);

        return bouquets >= m;
    }
}

8. Complexity Analysis

Summary and Key Takeaways

• Problem Classification: This is a classic "Binary Search on Answers" problem where the answer space ranges between the minimum and maximum values of the input array.
• Impossible Validation: Always check whether $M \times K > N$ right at the start to catch impossible configurations and return -1 immediately.
• Monotonicity Principle: Binary search is applicable because feasibility is monotonic: once a specific day $X$ makes it possible to form the bouquets, all days $> X$ remain feasible.
• Contiguous Tracking: Use a linear scan with a running counter (consecutive) to group adjacent flowers, resetting the counter whenever an unbloomed flower is encountered.
• Integer Overflow Prevention: Always cast products like m * k to long when comparing against array lengths to guard against integer overflow bugs.
• Optimization Impact: Shifting from a Linear Search ($\mathcal{O}(\text{Range} \cdot N)$) to a Binary Search ($\mathcal{O}(N \cdot \log(\text{Range}))$) drastically reduces execution time for large datasets.