Minimum Days to Make m Bouquets

🎯

Minimum Days to Make m Bouquets

mediumBINARY_SEARCHAmazonGoogle

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?

💡 This problem asks for the minimum day to achieve a goal given constraints on availability over time. Beginners often struggle because the answer isn't directly computed from the input but must be searched for efficiently using binary search on the answer space rather than the input array itself.

📋

Problem Statement

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

💡

Example

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

Output3

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

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

Output-1

We need 3 bouquets each with 2 adjacent flowers, but there are only 5 flowers total, so it's impossible.

• m * k > n → -1 (impossible to make required bouquets)
• All flowers bloom on the same day → minimum day is that day
• m = 1 and k = n → minimum day is max bloomDay (need all flowers)
• Large bloomDay values with sparse blooming → test efficiency

⚠️

Common Mistakes

Not checking if m * k > n before processing

Code runs unnecessarily and may return wrong answer or timeout

✅ Add early check to return -1 if total flowers needed exceed available flowers

Incorrect feasibility function that doesn't reset consecutive flower count

Bouquets counted incorrectly, leading to wrong answers

✅ Reset consecutive flower count to zero when a flower hasn't bloomed by the day

Binary search boundaries set incorrectly (e.g., 0 to max bloom day)

May miss the minimum feasible day or cause infinite loops

✅ Set low to min bloom day and high to max bloom day to cover all possible days

Not using early stopping in feasibility function

Unnecessary computation slows down solution on large inputs

✅ Return true immediately once required bouquets are made

Using linear search instead of binary search on answer space

Solution times out on large inputs

✅ Implement binary search on day range to reduce time complexity

🧠

Brute Force (Check Each Day Sequentially)

💡 This approach tries every possible day from the earliest bloom to the latest bloom to check if we can make the bouquets. It is simple and intuitive but inefficient for large inputs.

Intuition

We simulate each day starting from the earliest bloom day and check if enough bouquets can be made by counting consecutive bloomed flowers.

Algorithm

1. Find the minimum and maximum bloom days.
2. For each day from minimum to maximum:
3. Check if we can make m bouquets by counting k consecutive bloomed flowers.
4. Return the first day where making m bouquets is possible; otherwise, return -1.

💡 The main difficulty is understanding how to check bouquet feasibility for each day and why checking every day is slow.

</>

Code

def minDays(bloomDay, m, k):
    n = len(bloomDay)
    if m * k > n:
        return -1
    min_day, max_day = min(bloomDay), max(bloomDay)
    def canMake(day):
        bouquets = flowers = 0
        for bloom in bloomDay:
            if bloom <= day:
                flowers += 1
                if flowers == k:
                    bouquets += 1
                    flowers = 0
            else:
                flowers = 0
        return bouquets >= m
    for day in range(min_day, max_day + 1):
        if canMake(day):
            return day
    return -1

# Example usage
if __name__ == '__main__':
    print(minDays([1,10,3,10,2], 3, 1))  # Output: 3

Line Notes

if m * k > n:Quickly eliminate impossible cases where total flowers needed exceed available flowers

min_day, max_day = min(bloomDay), max(bloomDay)Establish the search range for days

def canMake(day):Define feasibility function to check if bouquets can be made by this day

for bloom in bloomDay:Iterate over flowers to count consecutive bloomed flowers

if bloom <= day:Check if flower has bloomed by current day

if flowers == k:Once k consecutive flowers are found, increment bouquet count

for day in range(min_day, max_day + 1):Try every day in the range sequentially

if canMake(day):Return the first day that satisfies the bouquet requirement

import java.util.*;
public class Solution {
    public static int minDays(int[] bloomDay, int m, int k) {
        int n = bloomDay.length;
        if (m * k > n) return -1;
        int minDay = Integer.MAX_VALUE, maxDay = Integer.MIN_VALUE;
        for (int day : bloomDay) {
            minDay = Math.min(minDay, day);
            maxDay = Math.max(maxDay, day);
        }
        for (int day = minDay; day <= maxDay; day++) {
            if (canMake(bloomDay, m, k, day)) return day;
        }
        return -1;
    }
    private static boolean canMake(int[] bloomDay, int m, int k, int day) {
        int bouquets = 0, flowers = 0;
        for (int bloom : bloomDay) {
            if (bloom <= day) {
                flowers++;
                if (flowers == k) {
                    bouquets++;
                    flowers = 0;
                }
            } else {
                flowers = 0;
            }
        }
        return bouquets >= m;
    }
    public static void main(String[] args) {
        System.out.println(minDays(new int[]{1,10,3,10,2}, 3, 1)); // Output: 3
    }
}

Line Notes

if (m * k > n) return -1;Eliminate impossible cases early

for (int day : bloomDay)Find min and max bloom days to define search range

for (int day = minDay; day <= maxDay; day++)Check each day sequentially

if (canMake(bloomDay, m, k, day)) return day;Return earliest feasible day

if (bloom <= day)Check if flower has bloomed by current day

if (flowers == k)Count bouquets when k consecutive flowers bloom

flowers = 0;Reset consecutive count when flower not bloomed

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canMake(const vector<int>& bloomDay, int m, int k, int day) {
    int bouquets = 0, flowers = 0;
    for (int bloom : bloomDay) {
        if (bloom <= day) {
            flowers++;
            if (flowers == k) {
                bouquets++;
                flowers = 0;
            }
        } else {
            flowers = 0;
        }
    }
    return bouquets >= m;
}

int minDays(vector<int>& bloomDay, int m, int k) {
    int n = bloomDay.size();
    if (m * k > n) return -1;
    int minDay = *min_element(bloomDay.begin(), bloomDay.end());
    int maxDay = *max_element(bloomDay.begin(), bloomDay.end());
    for (int day = minDay; day <= maxDay; day++) {
        if (canMake(bloomDay, m, k, day)) return day;
    }
    return -1;
}

int main() {
    vector<int> bloomDay = {1,10,3,10,2};
    cout << minDays(bloomDay, 3, 1) << endl; // Output: 3
    return 0;
}

Line Notes

if (m * k > n) return -1;Check if making bouquets is impossible upfront

int minDay = *min_element(bloomDay.begin(), bloomDay.end());Find earliest bloom day

int maxDay = *max_element(bloomDay.begin(), bloomDay.end());Find latest bloom day

for (int day = minDay; day <= maxDay; day++)Try every day sequentially

if (canMake(bloomDay, m, k, day)) return day;Return first feasible day

if (bloom <= day)Check if flower has bloomed by current day

if (flowers == k)Count bouquets when k consecutive flowers bloom

flowers = 0;Reset consecutive count when flower not bloomed

function canMake(bloomDay, m, k, day) {
    let bouquets = 0, flowers = 0;
    for (const bloom of bloomDay) {
        if (bloom <= day) {
            flowers++;
            if (flowers === k) {
                bouquets++;
                flowers = 0;
            }
        } else {
            flowers = 0;
        }
    }
    return bouquets >= m;
}

function minDays(bloomDay, m, k) {
    const n = bloomDay.length;
    if (m * k > n) return -1;
    let minDay = Math.min(...bloomDay);
    let maxDay = Math.max(...bloomDay);
    for (let day = minDay; day <= maxDay; day++) {
        if (canMake(bloomDay, m, k, day)) return day;
    }
    return -1;
}

// Example usage
console.log(minDays([1,10,3,10,2], 3, 1)); // Output: 3

Line Notes

if (m * k > n) return -1;Quickly rule out impossible cases

let minDay = Math.min(...bloomDay);Find earliest bloom day to start search

let maxDay = Math.max(...bloomDay);Find latest bloom day to end search

for (let day = minDay; day <= maxDay; day++)Check each day sequentially

if (canMake(bloomDay, m, k, day)) return day;Return earliest day that works

if (bloom <= day)Check if flower has bloomed by current day

if (flowers === k)Count bouquets when k consecutive flowers bloom

flowers = 0;Reset consecutive count when flower not bloomed

⏱

Complexity

TimeO(n * D) where D is the range of days (maxDay - minDay)

SpaceO(1) additional space

For each day in the range, we scan the bloomDay array once to check feasibility, leading to O(n*D) time.

💡 If n=10^5 and day range is large (up to 10^9), this approach is too slow to finish in reasonable time.

Interview Verdict: TLE

This approach is too slow for large inputs because it checks every day sequentially. It is useful only to understand the problem and feasibility check.

🧠

Binary Search on Answer Space

💡 This approach uses binary search on the range of days to efficiently find the minimum day to make m bouquets, leveraging the feasibility function from the brute force approach.

Intuition

Instead of checking every day, we guess a day mid-way and check if we can make bouquets by then. If yes, try earlier days; if no, try later days.

Algorithm

1. Set low to min bloom day and high to max bloom day.
2. While low <= high:
3. Calculate mid as (low + high) // 2.
4. Check if bouquets can be made by day mid using feasibility function.
5. If yes, update answer and search left half (high = mid - 1).
6. If no, search right half (low = mid + 1).
7. Return the answer if found; otherwise, -1.

💡 The key is to use the feasibility function as a yes/no test to guide binary search on the answer space.

</>

Code

def minDays(bloomDay, m, k):
    n = len(bloomDay)
    if m * k > n:
        return -1
    low, high = min(bloomDay), max(bloomDay)
    def canMake(day):
        bouquets = flowers = 0
        for bloom in bloomDay:
            if bloom <= day:
                flowers += 1
                if flowers == k:
                    bouquets += 1
                    flowers = 0
            else:
                flowers = 0
        return bouquets >= m
    answer = -1
    while low <= high:
        mid = (low + high) // 2
        if canMake(mid):
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    return answer

# Example usage
if __name__ == '__main__':
    print(minDays([1,10,3,10,2], 3, 1))  # Output: 3

Line Notes

if m * k > n:Eliminate impossible cases early

low, high = min(bloomDay), max(bloomDay)Initialize binary search boundaries

def canMake(day):Feasibility function reused from brute force

while low <= high:Binary search loop to narrow down minimum day

mid = (low + high) // 2Check middle day as candidate

if canMake(mid):If feasible, try earlier days to minimize

high = mid - 1Narrow search to left half

else: low = mid + 1If not feasible, try later days

return answerReturn earliest feasible day or -1 if none

import java.util.*;
public class Solution {
    public static int minDays(int[] bloomDay, int m, int k) {
        int n = bloomDay.length;
        if (m * k > n) 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 answer = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canMake(bloomDay, m, k, mid)) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return answer;
    }
    private static boolean canMake(int[] bloomDay, int m, int k, int day) {
        int bouquets = 0, flowers = 0;
        for (int bloom : bloomDay) {
            if (bloom <= day) {
                flowers++;
                if (flowers == k) {
                    bouquets++;
                    flowers = 0;
                }
            } else {
                flowers = 0;
            }
        }
        return bouquets >= m;
    }
    public static void main(String[] args) {
        System.out.println(minDays(new int[]{1,10,3,10,2}, 3, 1)); // Output: 3
    }
}

Line Notes

if (m * k > n) return -1;Early exit for impossible cases

int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;Initialize binary search bounds

for (int day : bloomDay)Find min and max bloom days

while (low <= high)Binary search loop

int mid = low + (high - low) / 2;Calculate mid to avoid overflow

if (canMake(bloomDay, m, k, mid))Check feasibility at mid day

answer = mid; high = mid - 1;Update answer and search left half

else low = mid + 1;Search right half if not feasible

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canMake(const vector<int>& bloomDay, int m, int k, int day) {
    int bouquets = 0, flowers = 0;
    for (int bloom : bloomDay) {
        if (bloom <= day) {
            flowers++;
            if (flowers == k) {
                bouquets++;
                flowers = 0;
            }
        } else {
            flowers = 0;
        }
    }
    return bouquets >= m;
}

int minDays(vector<int>& bloomDay, int m, int k) {
    int n = bloomDay.size();
    if (m * k > n) return -1;
    int low = *min_element(bloomDay.begin(), bloomDay.end());
    int high = *max_element(bloomDay.begin(), bloomDay.end());
    int answer = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canMake(bloomDay, m, k, mid)) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

int main() {
    vector<int> bloomDay = {1,10,3,10,2};
    cout << minDays(bloomDay, 3, 1) << endl; // Output: 3
    return 0;
}

Line Notes

if (m * k > n) return -1;Check impossible cases early

int low = *min_element(bloomDay.begin(), bloomDay.end());Set low boundary for binary search

int high = *max_element(bloomDay.begin(), bloomDay.end());Set high boundary for binary search

while (low <= high)Binary search loop

int mid = low + (high - low) / 2;Calculate mid to avoid overflow

if (canMake(bloomDay, m, k, mid))Check feasibility at mid day

answer = mid; high = mid - 1;Update answer and search left half

else low = mid + 1;Search right half if not feasible

function canMake(bloomDay, m, k, day) {
    let bouquets = 0, flowers = 0;
    for (const bloom of bloomDay) {
        if (bloom <= day) {
            flowers++;
            if (flowers === k) {
                bouquets++;
                flowers = 0;
            }
        } else {
            flowers = 0;
        }
    }
    return bouquets >= m;
}

function minDays(bloomDay, m, k) {
    const n = bloomDay.length;
    if (m * k > n) return -1;
    let low = Math.min(...bloomDay);
    let high = Math.max(...bloomDay);
    let answer = -1;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (canMake(bloomDay, m, k, mid)) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

// Example usage
console.log(minDays([1,10,3,10,2], 3, 1)); // Output: 3

Line Notes

if (m * k > n) return -1;Eliminate impossible cases early

let low = Math.min(...bloomDay);Initialize low boundary for binary search

let high = Math.max(...bloomDay);Initialize high boundary for binary search

while (low <= high)Binary search loop

let mid = Math.floor((low + high) / 2);Calculate mid point

if (canMake(bloomDay, m, k, mid))Check feasibility at mid day

answer = mid; high = mid - 1;Update answer and search left half

else low = mid + 1;Search right half if not feasible

⏱

Complexity

TimeO(n log D) where D is the range of days (maxDay - minDay)

SpaceO(1) additional space

Binary search reduces day checks from D to log D, each feasibility check is O(n), total O(n log D).

💡 For n=10^5 and D=10^9, this approach is efficient enough to run within time limits.

Interview Verdict: Accepted

This is the optimal approach for this problem, balancing correctness and efficiency.

🧠

Binary Search with Early Stopping in Feasibility Check

💡 This approach improves the feasibility function by stopping early once enough bouquets are made, saving unnecessary computation.

Intuition

If we already have enough bouquets, no need to continue counting; this can speed up feasibility checks especially when m is small.

Algorithm

1. Perform binary search on day range as before.
2. In feasibility function, count bouquets and stop immediately when bouquets >= m.
3. Adjust binary search boundaries based on feasibility result.
4. Return the minimum feasible day.

💡 Early stopping reduces unnecessary iteration, improving runtime in practice.

</>

Code

def minDays(bloomDay, m, k):
    n = len(bloomDay)
    if m * k > n:
        return -1
    low, high = min(bloomDay), max(bloomDay)
    def canMake(day):
        bouquets = flowers = 0
        for bloom in bloomDay:
            if bloom <= day:
                flowers += 1
                if flowers == k:
                    bouquets += 1
                    flowers = 0
                    if bouquets >= m:
                        return True
            else:
                flowers = 0
        return bouquets >= m
    answer = -1
    while low <= high:
        mid = (low + high) // 2
        if canMake(mid):
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    return answer

if __name__ == '__main__':
    print(minDays([1,10,3,10,2], 3, 1))  # Output: 3

Line Notes

if bouquets >= m:Stop counting once enough bouquets are made to save time

for bloom in bloomDay:Iterate over flowers to count bouquets

if bloom <= day:Check if flower has bloomed by current day

while low <= high:Binary search loop to find minimum day

if canMake(mid):If feasible, try earlier days

else: low = mid + 1If not feasible, try later days

import java.util.*;
public class Solution {
    public static int minDays(int[] bloomDay, int m, int k) {
        int n = bloomDay.length;
        if (m * k > n) 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 answer = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canMake(bloomDay, m, k, mid)) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return answer;
    }
    private static boolean canMake(int[] bloomDay, int m, int k, int day) {
        int bouquets = 0, flowers = 0;
        for (int bloom : bloomDay) {
            if (bloom <= day) {
                flowers++;
                if (flowers == k) {
                    bouquets++;
                    flowers = 0;
                    if (bouquets >= m) return true;
                }
            } else {
                flowers = 0;
            }
        }
        return bouquets >= m;
    }
    public static void main(String[] args) {
        System.out.println(minDays(new int[]{1,10,3,10,2}, 3, 1)); // Output: 3
    }
}

Line Notes

if (bouquets >= m) return true;Early return to avoid unnecessary counting

for (int bloom : bloomDay)Iterate over flowers to count bouquets

if (bloom <= day)Check if flower has bloomed by current day

while (low <= high)Binary search loop

if (canMake(bloomDay, m, k, mid))Check feasibility at mid day

high = mid - 1;Search left half if feasible

else low = mid + 1;Search right half if not feasible

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canMake(const vector<int>& bloomDay, int m, int k, int day) {
    int bouquets = 0, flowers = 0;
    for (int bloom : bloomDay) {
        if (bloom <= day) {
            flowers++;
            if (flowers == k) {
                bouquets++;
                flowers = 0;
                if (bouquets >= m) return true;
            }
        } else {
            flowers = 0;
        }
    }
    return bouquets >= m;
}

int minDays(vector<int>& bloomDay, int m, int k) {
    int n = bloomDay.size();
    if (m * k > n) return -1;
    int low = *min_element(bloomDay.begin(), bloomDay.end());
    int high = *max_element(bloomDay.begin(), bloomDay.end());
    int answer = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canMake(bloomDay, m, k, mid)) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

int main() {
    vector<int> bloomDay = {1,10,3,10,2};
    cout << minDays(bloomDay, 3, 1) << endl; // Output: 3
    return 0;
}

Line Notes

if (bouquets >= m) return true;Stop counting once requirement met

for (int bloom : bloomDay)Iterate over flowers to count bouquets

if (bloom <= day)Check if flower has bloomed by current day

while (low <= high)Binary search loop

int mid = low + (high - low) / 2;Calculate mid to avoid overflow

if (canMake(bloomDay, m, k, mid))Check feasibility at mid day

answer = mid; high = mid - 1;Update answer and search left half

else low = mid + 1;Search right half if not feasible

function canMake(bloomDay, m, k, day) {
    let bouquets = 0, flowers = 0;
    for (const bloom of bloomDay) {
        if (bloom <= day) {
            flowers++;
            if (flowers === k) {
                bouquets++;
                flowers = 0;
                if (bouquets >= m) return true;
            }
        } else {
            flowers = 0;
        }
    }
    return bouquets >= m;
}

function minDays(bloomDay, m, k) {
    const n = bloomDay.length;
    if (m * k > n) return -1;
    let low = Math.min(...bloomDay);
    let high = Math.max(...bloomDay);
    let answer = -1;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (canMake(bloomDay, m, k, mid)) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

console.log(minDays([1,10,3,10,2], 3, 1)); // Output: 3

Line Notes

if (bouquets >= m) return true;Early exit to improve efficiency

for (const bloom of bloomDay)Iterate over flowers to count bouquets

if (bloom <= day)Check if flower has bloomed by current day

while (low <= high)Binary search loop

let mid = Math.floor((low + high) / 2);Calculate mid point

if (canMake(bloomDay, m, k, mid))Check feasibility at mid day

answer = mid; high = mid - 1;Update answer and search left half

else low = mid + 1;Search right half if not feasible

⏱

Complexity

TimeO(n log D) with practical speedup due to early stopping

SpaceO(1)

Early stopping reduces average feasibility check time, improving runtime in practice though worst-case remains O(n log D).

💡 This small optimization can make a big difference on large inputs with small m.

Interview Verdict: Accepted

This is a practical optimization that can improve runtime without changing overall complexity.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always implement the binary search approach with early stopping for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * D) where D is day range	O(1)	No	N/A	Mention only - too slow to code
2. Binary Search on Answer Space	O(n log D)	O(1)	No	N/A	Code this approach for optimal solution
3. Binary Search with Early Stopping	O(n log D) with practical speedup	O(1)	No	N/A	Code this if time permits for efficiency

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force to show understanding, and finally present the optimized binary search approach.

How to Present

Step 1: Clarify the problem constraints and inputs.Step 2: Describe the brute force approach to check feasibility day by day.Step 3: Introduce binary search on the answer space to optimize.Step 4: Explain the feasibility function and how it guides binary search.Step 5: Discuss edge cases and test your code with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to recognize binary search on answer space, implement a correct feasibility function, and optimize for large inputs.

Common Follow-ups

• What if flowers can be picked non-adjacently? → Adjust feasibility function accordingly.
• How to handle very large bloomDay values efficiently? → Use binary search to avoid linear scanning of days.

💡 Follow-ups often test your flexibility in modifying feasibility checks and handling large input ranges efficiently.

🔍

Pattern Recognition

When to Use

1) Problem asks for minimum/maximum value satisfying a condition; 2) Condition can be checked efficiently; 3) Input size too large for brute force; 4) Values form a monotonic sequence over the search space.

Signature Phrases

minimum number of dayscan make m bouquetsk adjacent flowers

NOT This Pattern When

Problems that require direct binary search on sorted arrays or classic DP problems.

Similar Problems

Split Array Largest Sum - binary search on max subarray sumCapacity To Ship Packages Within D Days - binary search on capacityKoko Eating Bananas - binary search on eating speed

Practice

1. You are given a sorted array that has been rotated at an unknown pivot. The array contains no duplicates. You need to find the minimum element in O(log n) time. Which algorithmic approach guarantees this optimal time complexity?

easy

A. Greedy approach selecting the smallest element seen so far while iterating

B. Linear scan through the array to find the point where order breaks

C. Dynamic programming to store minimum values for subarrays

D. Modified binary search that compares middle element with neighbors to find the pivot

Solution

1. Step 1: Understand the problem constraints and properties

   The array is sorted but rotated, so the minimum element is the pivot point where the order breaks.

2. Step 2: Identify the algorithm that exploits the rotated sorted property

   Modified binary search compares the middle element with its neighbors to find the pivot in O(log n) time, unlike linear or greedy approaches.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search reduces the search space logarithmically [OK]

Hint: Pivot finding via binary search is key [OK]

Common Mistakes:

• Thinking linear scan is optimal
• Confusing DP with binary search
• Assuming greedy works on rotated arrays

2. Consider the following Python code implementing the optimal solution for splitting an array into m subarrays minimizing the largest sum. Given nums = [7, 2, 5, 10] and m = 2, what is the final returned value?

easy

A. 10

B. 12

C. 17

D. 15

Solution

1. Step 1: Calculate prefix sums

   prefix = [0, 7, 9, 14, 24]

2. Step 2: Binary search on answer space [7,24]

   Check mid=15: can split into subarrays with max sum ≤15? Yes (e.g., [7,2,5] and [10]). Try lower mid=11: cannot split into 2 subarrays with max sum ≤11. Finally, minimal largest sum found is 12.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Minimal largest sum for splitting [7,2,5,10] into 2 parts is 12 [OK]

Hint: Trace binary search mid and feasibility check carefully [OK]

Common Mistakes:

• Off-by-one in bisect leading to wrong subarray boundaries
• Confusing max element with sum for low/high bounds
• Miscounting number of splits in feasibility check

3. What is the time complexity of the optimal binary search with early stopping feasibility check approach for the Capacity to Ship Packages problem, where n is the number of packages and S is the sum of all package weights?

medium

A. O(n * S) because we check all capacities from max weight to sum weights

B. O(n log S) because binary search reduces capacity range and feasibility check is linear

C. O(n^2) because feasibility check may scan packages multiple times

D. O(log n * S) because binary search is on number of packages and capacity sum

Solution

1. Step 1: Identify binary search iterations

   Binary search on capacity range S takes O(log S) steps.

2. Step 2: Analyze feasibility check cost

   Feasibility check scans all n packages once per binary search iteration -> O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search x linear feasibility check -> O(n log S) [OK]

Hint: Binary search log factor times linear feasibility check [OK]

Common Mistakes:

• Confusing linear scan with quadratic
• Thinking feasibility check is O(log S)
• Assuming binary search on packages not capacity

4. The following code attempts to find the k closest elements to x in a sorted array. Identify the line that contains a subtle bug that can cause incorrect results when distances tie.

medium

A. Line 7: mid = (low + high) // 2

B. Line 8: if abs(x - arr[mid]) > abs(arr[mid + k] - x):

C. Line 5: while low < high:

D. Line 10: return arr[low:low + k]

Solution

1. Step 1: Understand tie-breaker logic

   The problem requires choosing the smaller element when distances tie, but abs() removes sign information.

2. Step 2: Identify bug in distance comparison

   Using abs() ignores which side is closer and breaks tie-breaker rules, causing incorrect window selection.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct code compares x - arr[mid] and arr[mid+k] - x without abs [OK]

Hint: Tie-breakers require signed distance comparison, not absolute values [OK]

Common Mistakes:

• Using absolute values loses tie-breaker info
• Off-by-one errors in mid calculation
• Returning wrong slice boundaries

5. Suppose Koko can eat bananas from multiple piles simultaneously each hour (i.e., she can split her eating speed across piles). How does this change the approach to find the minimum eating speed to finish within h hours?

hard

A. Feasibility check simplifies to total bananas ≤ speed * h, so minimum speed = ceil(total / h)

B. We must use dynamic programming to consider all pile combinations per hour

C. The original binary search with feasibility check still applies without changes

D. Binary search is invalid; a greedy approach is required instead

Solution

1. Step 1: Understand the new eating model

   Koko can split speed across piles simultaneously, so total bananas eaten per hour equals speed.

2. Step 2: Simplify feasibility condition

   To finish in h hours, total bananas ≤ speed * h, so minimum speed = ceil(total bananas / h).

3. Step 3: Conclude algorithm change

   No binary search needed; direct calculation suffices.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Splitting speed removes per-pile constraints, simplifying problem [OK]

Hint: Splitting speed means total bananas divided by hours [OK]

Common Mistakes:

• Applying original binary search blindly
• Overcomplicating with DP