ApproachOnBinarySearchOnAnswers.md

🌸 Minimum Number of Days to Make Bouquets

Problem Statement

You are given an integer array bloomDay[] where:

• bloomDay[i] represents the day the i-th flower blooms
• You must create M bouquets
• Each bouquet requires K consecutive flowers

Tasks

1. Return the minimum number of days required to make M bouquets
2. If it is not possible, return -1

---

Key Observations

1️) Feasibility Check (Fail Fast)

To make M bouquets of K flowers each:

Total flowers required = M × K

If:

M × K > bloomDay.length

It is impossible to form the bouquets, so return -1.

---

2️) Why Binary Search Works

This problem is not about searching indices.

It is about searchin

Define a function:

CanMakeBouquet(day)

• If bouquets can be made on day D
• They can also be made on any day greater than D

This creates a monotonic pattern:

F F F F F T T T T

Perfect use case for Binary Search on Answer.

---

Approach

• Search space: minimum bloom day → maximum bloom day
• Apply binary search on days
• Check if M bouquets can be formed using K consecutive flowers
• Minimize the day

---

Java Implementation

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

        if ((long) m * k > bloomDay.length) return -1;

        int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;
        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 (canMakeBouquet(bloomDay, m, k, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean canMakeBouquet(int[] bloomDay, int m, int k, int days) {
        int count = 0;

        for (int day : bloomDay) {
            if (day <= days) {
                count++;
                if (count == k) {
                    m--;
                    count = 0;
                }
            } else {
                count = 0;
            }
        }
        return m <= 0;
    }
}

---

⏱ Complexity Analysis

• Time Complexity: O(n log(maxDay))
• Space Complexity: O(1)

---

Binary Search is not only for sorted arrays.
It can be applied whenever the answer space is monotonic.

---