Minimum Days to Make m Bouquets

📋

Problem

Imagine a gardener who wants to make a certain number of bouquets from blooming flowers, but each flower blooms on a different day. How soon can the gardener make all bouquets?

You are given an integer array bloomDay, an integer m, and an integer k. You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden. The garden has n flowers, and the ith flower will bloom on the bloomDay[i] day. You want to find the minimum number of days you need to wait until you can make m bouquets from the flowers that have bloomed. If it is impossible to make m bouquets, return -1.

1 ≤ bloomDay.length = n ≤ 10^51 ≤ bloomDay[i] ≤ 10^91 ≤ m ≤ 10^61 ≤ k ≤ n

Edge cases: m * k > n → -1 (impossible to make required bouquets)All flowers bloom on the same day → minimum day is that daym = 1 and k = n → minimum day is max bloomDay (need all flowers)

</>

IDE

def minDays(bloomDay: list[int], m: int, k: int) -> int:public int minDays(int[] bloomDay, int m, int k)int minDays(vector<int>& bloomDay, int m, int k)function minDays(bloomDay, m, k)

def minDays(bloomDay, m, k):
    # Write your solution here
    pass

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        // Write your solution here
        return -1;
    }
}

#include <vector>
using namespace std;

int minDays(vector<int>& bloomDay, int m, int k) {
    // Write your solution here
    return -1;
}

function minDays(bloomDay, m, k) {
    // Write your solution here
    return -1;
}

Common Bugs to Avoid

Wrong: -1Returning -1 prematurely without checking feasibility when m*k <= n.✅ Add a feasibility check before returning -1; only return -1 if m*k > n or no day satisfies feasibility.

Wrong: max(bloomDay)Always returning max bloom day without binary searching for earlier feasible day.✅ Implement binary search on day range and check feasibility at midpoints to find minimum day.

Wrong: Incorrect minimum day less than actualFeasibility function counts flowers but ignores adjacency requirement.✅ Modify feasibility to count only k adjacent bloomed flowers as one bouquet; reset count when flower not bloomed by day d.

Wrong: Timeout or crash on large inputsLinear scanning days instead of binary search; no early stopping in feasibility.✅ Use binary search on answer space and implement early stopping when bouquets reached in feasibility.

Wrong: Incorrect output on empty inputNo guard clause for empty bloomDay array causing errors or wrong return.✅ Add early return -1 if bloomDay is empty or n=0.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly to avoid crashes or incorrect results.

Watch out for common algorithmic traps like greedy approaches and off-by-one errors in adjacency checks.

Optimize your solution to use binary search on the answer space and implement early stopping to pass performance tests.

t1_01basic

Input{"bloomDay":[1,10,3,10,2],"m":3,"k":1,"n":5}

Expected3

⏱ Performance - must finish in 2000ms

On day 3, flowers at indices 0, 2, and 4 have bloomed, so we can make 3 bouquets each with 1 flower.

💡 Consider binary searching the day range between min and max bloom days.

💡 Use a feasibility function to check if m bouquets can be made by day d.

💡 Check adjacent flowers blooming by day d to count bouquets.

Why it failed: Incorrect output means feasibility check or binary search bounds are wrong; ensure canMake(day) counts bouquets correctly and binary search narrows day range properly.

✓ Correctly finds minimum day using binary search and feasibility check.

t1_02basic

Input{"bloomDay":[1,2,4,9,3,4,1],"m":2,"k":2,"n":7}

Expected4

⏱ Performance - must finish in 2000ms

By day 4, flowers at indices [0,1] and [5,6] have bloomed, allowing 2 bouquets of 2 adjacent flowers each.

💡 Remember bouquets require k adjacent bloomed flowers, not just any k flowers.

💡 Check feasibility by scanning bloomDay for consecutive bloomed flowers by day d.

💡 Binary search the day range and use feasibility to find minimum day.

Why it failed: Failing this test usually means adjacency logic in feasibility is incorrect; fix by resetting consecutive count when a flower hasn't bloomed by day d.

✓ Correctly handles adjacency and finds minimum day for multiple bouquets.

t2_01edge

Input{"bloomDay":[],"m":1,"k":1,"n":0}

Expected-1

⏱ Performance - must finish in 2000ms

Empty garden means no flowers; impossible to make any bouquets.

💡 Check if input array is empty or n=0 before processing.

💡 If m*k > n, return -1 immediately.

💡 Add a guard clause for empty bloomDay to avoid errors.

Why it failed: Code crashes or returns wrong value on empty input; fix by adding early return if n=0 or bloomDay is empty.

✓ Handles empty input gracefully by returning -1.

t2_02edge

Input{"bloomDay":[5],"m":1,"k":1,"n":1}

Expected5

⏱ Performance - must finish in 2000ms

Single flower blooms on day 5; need 1 bouquet of 1 flower, so minimum day is 5.

💡 Test single element arrays to ensure feasibility check works with minimal input.

💡 Check that binary search handles min_day == max_day correctly.

💡 Ensure feasibility function returns true when one flower meets requirements.

Why it failed: Fails single element test if feasibility or binary search does not handle single element correctly; fix by ensuring binary search includes min_day and max_day properly.

✓ Correctly returns bloom day for single flower bouquet.

t2_03edge

Input{"bloomDay":[7,7,7,7,7],"m":2,"k":2,"n":5}

Expected7

⏱ Performance - must finish in 2000ms

All flowers bloom on the same day 7; need 2 bouquets of 2 adjacent flowers, possible on day 7.

💡 Check if all bloomDay values are identical and feasibility reflects that.

💡 Binary search should return that identical bloom day if feasible.

💡 Feasibility must count adjacent flowers correctly even if all bloom same day.

Why it failed: Fails if feasibility does not handle identical bloom days or adjacency correctly; fix by ensuring consecutive count resets only on flowers blooming after day d.

✓ Handles uniform bloom days and adjacency correctly.

t3_01corner

Input{"bloomDay":[1,10,2,9,3,8,4,7,5,6],"m":3,"k":2,"n":10}

Expected8

⏱ Performance - must finish in 2000ms

Greedy approach picking earliest bloomed flowers fails; minimum day is 5 to get 3 bouquets of 2 adjacent flowers.

💡 Beware greedy picking earliest bloomed flowers without adjacency check.

💡 Use binary search with feasibility checking consecutive flowers.

💡 Feasibility must count only k adjacent flowers blooming by day d.

Why it failed: Fails due to greedy approach ignoring adjacency or feasibility; fix by implementing binary search with proper feasibility function counting consecutive flowers.

✓ Correctly avoids greedy trap and finds minimum day.

t3_02corner

Input{"bloomDay":[1,2,3,4,5],"m":1,"k":5,"n":5}

Expected5

⏱ Performance - must finish in 2000ms

Requires all flowers to bloom to make one bouquet; tests exact boundary condition m*k == n.

💡 Check boundary condition where m*k equals total flowers.

💡 Feasibility must require all flowers to bloom by day d.

💡 Binary search should return max bloom day in this case.

Why it failed: Fails if feasibility does not enforce exact boundary m*k == n; fix by ensuring feasibility counts consecutive flowers correctly and binary search covers full range.

✓ Correctly handles exact boundary condition.

t3_03corner

Input{"bloomDay":[1,1000000000,1,1000000000,1],"m":2,"k":2,"n":5}

Expected1000000000

⏱ Performance - must finish in 2000ms

Tests large bloomDay values with sparse blooming; must handle large day values efficiently.

💡 Binary search must handle large day ranges efficiently.

💡 Feasibility function should early stop when bouquets reached.

💡 Avoid linear scan over all days; use binary search on answer space.

Why it failed: Fails due to linear scan or overflow in day range; fix by implementing binary search on day range and early stopping in feasibility.

✓ Efficiently handles large day values with binary search.

t4_01performance

Input{"bloomDay":[1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,999999990,999999989,999999988,999999987,999999986,999999985,999999984,999999983,999999982,999999981,999999980,999999979,999999978,999999977,999999976,999999975,999999974,999999973,999999972,999999971,999999970,999999969,999999968,999999967,999999966,999999965,999999964,999999963,999999962,999999961,999999960,999999959,999999958,999999957,999999956,999999955,999999954,999999953,999999952,999999951,999999950,999999949,999999948,999999947,999999946,999999945,999999944,999999943,999999942,999999941,999999940,999999939,999999938,999999937,999999936,999999935,999999934,999999933,999999932,999999931,999999930,999999929,999999928,999999927,999999926,999999925,999999924,999999923,999999922,999999921,999999920,999999919,999999918,999999917,999999916,999999915,999999914,999999913,999999912,999999911,999999910,999999909,999999908,999999907,999999906,999999905,999999904,999999903,999999902,999999901,999999900],"m":500,"k":200,"n":100}

Expected-1

⏱ Performance - must finish in 2000ms

n=100, bloomDay values large; O(n log D) binary search must complete within 2 seconds.

💡 Use binary search on day range instead of linear scanning days.

💡 Implement early stopping in feasibility check when bouquets reached.

💡 Avoid unnecessary computations inside feasibility function.

Why it failed: TLE occurs if linear scan over days or no early stopping in feasibility; fix by using binary search on answer space and early stopping.

✓ Algorithm runs in O(n log D) time and completes within time limit.

Practice

1. Consider the following Python function that finds the kth positive missing number from a sorted array arr. What is the returned value when calling findKthPositive([2, 4, 7], 3)?

def findKthPositive(arr, k):
    n = len(arr)
    total_missing = arr[-1] - n
    if k > total_missing:
        return arr[-1] + (k - total_missing)
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        missing = arr[mid] - (mid + 1)
        if missing < k:
            left = mid + 1
        else:
            right = mid - 1
    return arr[right] + (k - (arr[right] - (right + 1)))

easy

A. 5

B. 8

C. 9

D. 7

Solution

1. Step 1: Calculate total missing numbers

   Array length n=3, arr[-1]=7, total_missing = 7 - 3 = 4. Since k=3 ≤ 4, proceed with binary search.

2. Step 2: Perform binary search iterations

   Initial left=0, right=2. - mid=1, missing=arr[1] - (1+1) = 4 - 2 = 2 < 3 -> left=2 - mid=2, missing=arr[2] - (2+1) = 7 - 3 = 4 ≥ 3 -> right=1 Loop ends as left=2 > right=1. Return arr[right] + (k - (arr[right] - (right + 1))) = arr[1] + (3 - (4 - 2)) = 4 + (3 - 2) = 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search narrows to index 1, final missing number is 5 [OK]

Hint: Trace missing count at mid carefully [OK]

Common Mistakes:

• Off-by-one in missing calculation
• Returning arr[left] instead of arr[right]
• Miscomputing missing count as arr[mid] - mid

2. Consider the following recursive binary search code for finding the insert position of target = 2 in nums = [1, 3, 5, 6]. What is the final returned value?

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace binary_search(0, 3)

   mid = (0+3)//2 = 1, nums[1] = 3 > 2, recurse left: binary_search(0, 0)

2. Step 2: Trace binary_search(0, 0)

   mid = (0+0)//2 = 0, nums[0] = 1 < 2, recurse right: binary_search(1, 0)

3. Step 3: Base case binary_search(1, 0)

   left > right, return left = 1 as insertion index

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Target 2 fits between 1 and 3 at index 1 [OK]

Hint: Follow recursive calls and base case carefully [OK]

Common Mistakes:

• Returning right instead of left at base case
• Off-by-one in mid calculation
• Confusing left and right updates

3. Consider the following buggy code for finding a peak element. Which line contains the subtle bug that can cause incorrect results or infinite recursion?

def findPeakElement(nums):
    def binarySearch(low, high):
        if low == high:
            return low
        mid = (low + high) // 2
        if nums[mid] < nums[mid]:  # Line X
            return binarySearch(mid + 1, high)
        else:
            return binarySearch(low, mid)
    return binarySearch(0, len(nums) - 1)

medium

A. Line 5: if nums[mid] < nums[mid]:

B. Line 4: mid = (low + high) // 2

C. Line 3: if low == high: return low

D. Line 7: return binarySearch(low, mid)

Solution

1. Step 1: Identify suspicious comparison

   Line 5 compares nums[mid] with itself, which is always false, causing wrong recursion path.

2. Step 2: Understand impact

   This bug causes infinite recursion or incorrect peak detection because the condition never triggers correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Comparison must be nums[mid] < nums[mid + 1] [OK]

Hint: Check comparisons carefully for off-by-one errors [OK]

Common Mistakes:

• Comparing mid with mid instead of mid+1
• Off-by-one causing infinite recursion
• Returning wrong index after recursion

4. What is the time complexity of the min-heap based approach to find the kth smallest element in an n x n sorted matrix, where k ≤ n²? Assume the heap operations take O(log n) time.

medium

A. O(k log n)

B. O(k log k)

C. O(n log k)

D. O(n^2 log n)

Solution

1. Step 1: Analyze heap size and operations

   The heap holds at most n elements (one from each row), so heap operations cost O(log n).

2. Step 2: Count total heap operations

   We pop and push at most k times, so total time is O(k log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap size bounded by n, operations proportional to k [OK]

Hint: Heap size limited to n, not k or n² [OK]

Common Mistakes:

• Assuming heap size grows to k or n²
• Confusing k and n in log factors
• Thinking complexity is O(n^2 log n)

5. Examine the following buggy code snippet for the Split Array Largest Sum problem. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line 7: Missing update of start to end causing infinite loop

B. Line 2: Initialization of count variable

C. Line 5: Using bisect_right to find end index

D. Line 8: Checking if count exceeds m

Solution

1. Step 1: Analyze loop control variables

   The variable start controls the loop progress and must be updated to avoid infinite loops.

2. Step 2: Identify missing update

   Line 7 lacks start = end, so start never advances, causing infinite loop or wrong split counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without updating start, loop never progresses [OK]

Hint: Check loop variables update carefully [OK]

Common Mistakes:

• Forgetting to update loop index after binary search
• Misusing bisect boundaries causing off-by-one errors
• Incorrect initialization of count or start