Capacity to Ship Packages

🎯

Capacity to Ship Packages

mediumBINARY_SEARCHAmazonGoogle

Imagine you are managing a shipping company that needs to send packages across several days. You want to find the minimum ship capacity that allows all packages to be shipped within a given number of days.

💡 This problem is a classic example of using binary search not on a sorted array, but on the range of possible answers. Beginners often struggle because they try to binary search the input array instead of the answer space, and they miss the feasibility check that guides the search.

📋

Problem Statement

You are given an array weights where weights[i] is the weight of the i-th package, and an integer days representing the number of days to ship all packages. Each day, you load the ship with packages in order without exceeding the ship's capacity. Return the minimum capacity of the ship such that all packages can be shipped within days.

1 ≤ weights.length ≤ 10^51 ≤ weights[i] ≤ 5001 ≤ days ≤ weights.length

💡

Example

Input"weights = [1,2,3,4,5,6,7,8,9,10], days = 5"

Output15

One optimal way is to ship packages in groups: [1,2,3,4,5], [6,7], [8], [9], [10]. The ship capacity must be at least 15 to ship all packages in 5 days.

• All packages have the same weight → output is that weight
• days equals the number of packages → output is max package weight
• days equals 1 → output is sum of all weights
• Only one package → output is weight of that package

⚠️

Common Mistakes

Binary searching the input array instead of the answer space

Incorrect or inefficient solution

✅ Binary search the range between max weight and sum of weights, not the array itself

Not handling the case when a single package weight exceeds capacity

Feasibility check always fails or infinite loop

✅ Set left boundary as max package weight to ensure capacity is never less

Forgetting to increment day count when capacity exceeded during feasibility check

Incorrect feasibility results, wrong answer

✅ Increment day count and reset current load when capacity exceeded

Not using integer division or incorrect mid calculation causing infinite loop

Infinite loop or wrong mid values

✅ Use mid = left + (right - left) // 2 to avoid overflow and ensure progress

Not stopping feasibility check early when days exceeded

Unnecessary computation, slower runtime

✅ Add early stopping condition in feasibility check

🧠

Brute Force (Check All Capacities)

💡 This approach exists to build intuition by trying every possible ship capacity from the maximum single package weight up to the sum of all weights. It is slow but helps understand the problem constraints and feasibility concept.

Intuition

Try every capacity from the max package weight to the sum of all weights and check if we can ship all packages within the given days. The smallest capacity that works is the answer.

Algorithm

1. Find the minimum capacity as the max weight in the array.
2. Find the maximum capacity as the sum of all weights.
3. For each capacity from min to max:
4. Check if all packages can be shipped within days with this capacity.
5. Return the first capacity that satisfies the condition.

💡 The main difficulty is understanding how to check feasibility for each capacity and why we must test all capacities in the range.

</>

Code

def can_ship(weights, days, capacity):
    day_count = 1
    current_load = 0
    for w in weights:
        if current_load + w > capacity:
            day_count += 1
            current_load = 0
        current_load += w
    return day_count <= days

def ship_with_capacity_brute_force(weights, days):
    left = max(weights)
    right = sum(weights)
    for capacity in range(left, right + 1):
        if can_ship(weights, days, capacity):
            return capacity

# Driver code
if __name__ == '__main__':
    weights = [1,2,3,4,5,6,7,8,9,10]
    days = 5
    print(ship_with_capacity_brute_force(weights, days))

Line Notes

def can_ship(weights, days, capacity):Defines a helper to check feasibility for a given capacity

for w in weights:Iterates over each package weight to simulate shipping

if current_load + w > capacity:If adding this package exceeds capacity, start a new day

return day_count <= daysReturns True if shipping is possible within given days

for capacity in range(left, right + 1):Tries every capacity from min to max to find feasible one

if can_ship(weights, days, capacity):Checks feasibility for current capacity

return capacityReturns the first capacity that works

import java.util.*;
public class ShipCapacityBruteForce {
    public static boolean canShip(int[] weights, int days, int capacity) {
        int dayCount = 1, currentLoad = 0;
        for (int w : weights) {
            if (currentLoad + w > capacity) {
                dayCount++;
                currentLoad = 0;
            }
            currentLoad += w;
        }
        return dayCount <= days;
    }

    public static int shipWithCapacityBruteForce(int[] weights, int days) {
        int left = Arrays.stream(weights).max().getAsInt();
        int right = Arrays.stream(weights).sum();
        for (int capacity = left; capacity <= right; capacity++) {
            if (canShip(weights, days, capacity)) {
                return capacity;
            }
        }
        return right;
    }

    public static void main(String[] args) {
        int[] weights = {1,2,3,4,5,6,7,8,9,10};
        int days = 5;
        System.out.println(shipWithCapacityBruteForce(weights, days));
    }
}

Line Notes

public static boolean canShip(int[] weights, int days, int capacity)Helper method to check if capacity suffices

for (int w : weights)Iterate over each package weight

if (currentLoad + w > capacity)Start new day if capacity exceeded

return dayCount <= daysReturn feasibility result

for (int capacity = left; capacity <= right; capacity++)Try all capacities from min to max

if (canShip(weights, days, capacity))Check feasibility for current capacity

return capacityReturn first feasible capacity

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

bool canShip(const vector<int>& weights, int days, int capacity) {
    int dayCount = 1, currentLoad = 0;
    for (int w : weights) {
        if (currentLoad + w > capacity) {
            dayCount++;
            currentLoad = 0;
        }
        currentLoad += w;
    }
    return dayCount <= days;
}

int shipWithCapacityBruteForce(const vector<int>& weights, int days) {
    int left = *max_element(weights.begin(), weights.end());
    int right = accumulate(weights.begin(), weights.end(), 0);
    for (int capacity = left; capacity <= right; capacity++) {
        if (canShip(weights, days, capacity)) {
            return capacity;
        }
    }
    return right;
}

int main() {
    vector<int> weights = {1,2,3,4,5,6,7,8,9,10};
    int days = 5;
    cout << shipWithCapacityBruteForce(weights, days) << endl;
    return 0;
}

Line Notes

bool canShip(const vector<int>& weights, int days, int capacity)Helper to check if capacity works

for (int w : weights)Iterate over package weights

if (currentLoad + w > capacity)Start new day if capacity exceeded

return dayCount <= daysReturn feasibility

for (int capacity = left; capacity <= right; capacity++)Try all capacities in range

if (canShip(weights, days, capacity))Check feasibility for capacity

return capacityReturn first feasible capacity

function canShip(weights, days, capacity) {
    let dayCount = 1, currentLoad = 0;
    for (let w of weights) {
        if (currentLoad + w > capacity) {
            dayCount++;
            currentLoad = 0;
        }
        currentLoad += w;
    }
    return dayCount <= days;
}

function shipWithCapacityBruteForce(weights, days) {
    let left = Math.max(...weights);
    let right = weights.reduce((a,b) => a+b, 0);
    for (let capacity = left; capacity <= right; capacity++) {
        if (canShip(weights, days, capacity)) {
            return capacity;
        }
    }
}

// Test
const weights = [1,2,3,4,5,6,7,8,9,10];
const days = 5;
console.log(shipWithCapacityBruteForce(weights, days));

Line Notes

function canShip(weights, days, capacity)Helper to check feasibility for capacity

for (let w of weights)Iterate over each package weight

if (currentLoad + w > capacity)Start new day if capacity exceeded

return dayCount <= daysReturn if shipping possible within days

for (let capacity = left; capacity <= right; capacity++)Try all capacities from min to max

if (canShip(weights, days, capacity))Check feasibility for current capacity

return capacityReturn first capacity that works

⏱

Complexity

TimeO(n * S) where S is sum(weights) - max(weights)

SpaceO(1)

For each capacity in the range, we scan all weights to check feasibility, leading to a potentially huge number of operations.

💡 For n=10 and sum(weights)=55, this means up to 45*10=450 operations, which is manageable, but for n=10^5 and large sums, this is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and feasibility check.

🧠

Binary Search on Answer Space

💡 This approach uses binary search on the range of possible ship capacities, drastically reducing the number of checks needed. It introduces the key concept of a feasibility function guiding the search.

Intuition

Instead of checking every capacity, use binary search between max package weight and sum of weights. For each mid capacity, check if shipping is possible. Narrow down the search space based on feasibility.

Algorithm

1. Set left as max weight and right as sum of weights.
2. While left < right:
3. Calculate mid as (left + right) // 2.
4. Check if shipping is possible with capacity mid.
5. If possible, move right to mid; else move left to mid + 1.
6. Return left as the minimum capacity.

💡 The challenge is understanding why binary searching the answer space works and how the feasibility function guides the search.

</>

Code

def can_ship(weights, days, capacity):
    day_count = 1
    current_load = 0
    for w in weights:
        if current_load + w > capacity:
            day_count += 1
            current_load = 0
        current_load += w
    return day_count <= days

def ship_with_capacity_binary_search(weights, days):
    left, right = max(weights), sum(weights)
    while left < right:
        mid = (left + right) // 2
        if can_ship(weights, days, mid):
            right = mid
        else:
            left = mid + 1
    return left

# Driver code
if __name__ == '__main__':
    weights = [1,2,3,4,5,6,7,8,9,10]
    days = 5
    print(ship_with_capacity_binary_search(weights, days))

Line Notes

def can_ship(weights, days, capacity):Defines feasibility check helper

for w in weights:Iterates over packages to simulate shipping

if current_load + w > capacity:Starts new day if capacity exceeded

return day_count <= daysReturns if shipping is possible within days

while left < right:Binary search loop over capacity range

mid = (left + right) // 2Calculate middle capacity to test

if can_ship(weights, days, mid):If feasible, try smaller capacity

else: left = mid + 1If not feasible, increase capacity

return leftMinimum capacity found

import java.util.*;
public class ShipCapacityBinarySearch {
    public static boolean canShip(int[] weights, int days, int capacity) {
        int dayCount = 1, currentLoad = 0;
        for (int w : weights) {
            if (currentLoad + w > capacity) {
                dayCount++;
                currentLoad = 0;
            }
            currentLoad += w;
        }
        return dayCount <= days;
    }

    public static int shipWithCapacityBinarySearch(int[] weights, int days) {
        int left = Arrays.stream(weights).max().getAsInt();
        int right = Arrays.stream(weights).sum();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canShip(weights, days, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] weights = {1,2,3,4,5,6,7,8,9,10};
        int days = 5;
        System.out.println(shipWithCapacityBinarySearch(weights, days));
    }
}

Line Notes

public static boolean canShip(int[] weights, int days, int capacity)Feasibility check helper

for (int w : weights)Iterate over packages

if (currentLoad + w > capacity)Start new day if capacity exceeded

return dayCount <= daysReturn feasibility

while (left < right)Binary search loop over capacity

int mid = left + (right - left) / 2Calculate mid capacity safely

if (canShip(weights, days, mid))If feasible, try smaller capacity

else left = mid + 1If not feasible, increase capacity

return leftReturn minimum capacity

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

bool canShip(const vector<int>& weights, int days, int capacity) {
    int dayCount = 1, currentLoad = 0;
    for (int w : weights) {
        if (currentLoad + w > capacity) {
            dayCount++;
            currentLoad = 0;
        }
        currentLoad += w;
    }
    return dayCount <= days;
}

int shipWithCapacityBinarySearch(const vector<int>& weights, int days) {
    int left = *max_element(weights.begin(), weights.end());
    int right = accumulate(weights.begin(), weights.end(), 0);
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canShip(weights, days, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    vector<int> weights = {1,2,3,4,5,6,7,8,9,10};
    int days = 5;
    cout << shipWithCapacityBinarySearch(weights, days) << endl;
    return 0;
}

Line Notes

bool canShip(const vector<int>& weights, int days, int capacity)Feasibility helper function

for (int w : weights)Iterate over packages

if (currentLoad + w > capacity)Start new day if capacity exceeded

return dayCount <= daysReturn feasibility

while (left < right)Binary search loop

int mid = left + (right - left) / 2Calculate mid capacity safely

if (canShip(weights, days, mid))If feasible, try smaller capacity

else left = mid + 1If not feasible, increase capacity

return leftReturn minimum capacity

function canShip(weights, days, capacity) {
    let dayCount = 1, currentLoad = 0;
    for (let w of weights) {
        if (currentLoad + w > capacity) {
            dayCount++;
            currentLoad = 0;
        }
        currentLoad += w;
    }
    return dayCount <= days;
}

function shipWithCapacityBinarySearch(weights, days) {
    let left = Math.max(...weights);
    let right = weights.reduce((a,b) => a+b, 0);
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canShip(weights, days, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// Test
const weights = [1,2,3,4,5,6,7,8,9,10];
const days = 5;
console.log(shipWithCapacityBinarySearch(weights, days));

Line Notes

function canShip(weights, days, capacity)Feasibility check helper

for (let w of weights)Iterate over packages

if (currentLoad + w > capacity)Start new day if capacity exceeded

return dayCount <= daysReturn feasibility

while (left < right)Binary search loop over capacity

let mid = Math.floor((left + right) / 2)Calculate mid capacity

if (canShip(weights, days, mid))If feasible, try smaller capacity

else left = mid + 1If not feasible, increase capacity

return leftReturn minimum capacity

⏱

Complexity

TimeO(n log S) where S = sum(weights) - max(weights)

SpaceO(1)

Binary search reduces the capacity search space logarithmically, and each feasibility check scans all weights once.

💡 For n=10^5 and sum(weights) ~ 5*10^7, this means about 10^5 * 25 = 2.5 million operations, which is efficient enough.

Interview Verdict: Accepted

This is the optimal approach for this problem and is expected in interviews.

🧠

Binary Search with Early Stopping in Feasibility Check

💡 This approach improves the feasibility check by stopping early once the days exceed the limit, saving unnecessary computation and slightly optimizing runtime.

Intuition

While checking feasibility, if the number of days needed exceeds the allowed days, stop immediately and return False. This avoids scanning the entire array unnecessarily.

Algorithm

1. Set left as max weight and right as sum of weights.
2. While left < right:
3. Calculate mid as (left + right) // 2.
4. Check feasibility with early stopping if days exceeded.
5. If feasible, move right to mid; else move left to mid + 1.
6. Return left as the minimum capacity.

💡 The key is to understand how early stopping reduces unnecessary work during feasibility checks.

</>

Code

def can_ship_early_stop(weights, days, capacity):
    day_count = 1
    current_load = 0
    for w in weights:
        if current_load + w > capacity:
            day_count += 1
            if day_count > days:
                return False
            current_load = 0
        current_load += w
    return True

def ship_with_capacity_binary_search_early_stop(weights, days):
    left, right = max(weights), sum(weights)
    while left < right:
        mid = (left + right) // 2
        if can_ship_early_stop(weights, days, mid):
            right = mid
        else:
            left = mid + 1
    return left

# Driver code
if __name__ == '__main__':
    weights = [1,2,3,4,5,6,7,8,9,10]
    days = 5
    print(ship_with_capacity_binary_search_early_stop(weights, days))

Line Notes

def can_ship_early_stop(weights, days, capacity):Defines feasibility check with early stopping

if day_count > days:Stops checking if days exceeded

return FalseImmediately returns False if not feasible

while left < right:Binary search loop

if can_ship_early_stop(weights, days, mid):Check feasibility with early stopping

return leftReturn minimum capacity

import java.util.*;
public class ShipCapacityBinarySearchEarlyStop {
    public static boolean canShipEarlyStop(int[] weights, int days, int capacity) {
        int dayCount = 1, currentLoad = 0;
        for (int w : weights) {
            if (currentLoad + w > capacity) {
                dayCount++;
                if (dayCount > days) return false;
                currentLoad = 0;
            }
            currentLoad += w;
        }
        return true;
    }

    public static int shipWithCapacityBinarySearchEarlyStop(int[] weights, int days) {
        int left = Arrays.stream(weights).max().getAsInt();
        int right = Arrays.stream(weights).sum();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canShipEarlyStop(weights, days, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] weights = {1,2,3,4,5,6,7,8,9,10};
        int days = 5;
        System.out.println(shipWithCapacityBinarySearchEarlyStop(weights, days));
    }
}

Line Notes

if (dayCount > days) return false;Early stop if days exceeded

return true;Return true if feasible

while (left < right)Binary search loop

if (canShipEarlyStop(weights, days, mid))Check feasibility with early stop

return left;Return minimum capacity

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

bool canShipEarlyStop(const vector<int>& weights, int days, int capacity) {
    int dayCount = 1, currentLoad = 0;
    for (int w : weights) {
        if (currentLoad + w > capacity) {
            dayCount++;
            if (dayCount > days) return false;
            currentLoad = 0;
        }
        currentLoad += w;
    }
    return true;
}

int shipWithCapacityBinarySearchEarlyStop(const vector<int>& weights, int days) {
    int left = *max_element(weights.begin(), weights.end());
    int right = accumulate(weights.begin(), weights.end(), 0);
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canShipEarlyStop(weights, days, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    vector<int> weights = {1,2,3,4,5,6,7,8,9,10};
    int days = 5;
    cout << shipWithCapacityBinarySearchEarlyStop(weights, days) << endl;
    return 0;
}

Line Notes

if (dayCount > days) return false;Early stop when days exceeded

return true;Return true if feasible

while (left < right)Binary search loop

if (canShipEarlyStop(weights, days, mid))Check feasibility with early stop

return left;Return minimum capacity

function canShipEarlyStop(weights, days, capacity) {
    let dayCount = 1, currentLoad = 0;
    for (let w of weights) {
        if (currentLoad + w > capacity) {
            dayCount++;
            if (dayCount > days) return false;
            currentLoad = 0;
        }
        currentLoad += w;
    }
    return true;
}

function shipWithCapacityBinarySearchEarlyStop(weights, days) {
    let left = Math.max(...weights);
    let right = weights.reduce((a,b) => a+b, 0);
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canShipEarlyStop(weights, days, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// Test
const weights = [1,2,3,4,5,6,7,8,9,10];
const days = 5;
console.log(shipWithCapacityBinarySearchEarlyStop(weights, days));

Line Notes

if (dayCount > days) return false;Early stop if days exceeded

return true;Return true if feasible

while (left < right)Binary search loop

if (canShipEarlyStop(weights, days, mid))Check feasibility with early stop

return leftReturn minimum capacity

⏱

Complexity

TimeO(n log S) with practical speedup

SpaceO(1)

Early stopping reduces average runtime of feasibility checks, especially when capacity is too small.

💡 This optimization helps in practice but does not change worst-case complexity.

Interview Verdict: Accepted

This is a practical optimization often appreciated in interviews to show attention to detail.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, coding the binary search on answer space approach with feasibility check is best. Brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * S) where S = sum(weights) - max(weights)	O(1)	No	N/A	Mention only - never code
2. Binary Search on Answer Space	O(n log S)	O(1)	No	N/A	Code this approach
3. Binary Search with Early Stopping	O(n log S) with practical speedup	O(1)	No	N/A	Code or mention as optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the binary search on answer space approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach and why it is inefficient.Step 3: Introduce binary search on the answer space and explain the feasibility function.Step 4: Write clean code for the binary search approach.Step 5: Test with examples and edge cases.Step 6: Discuss possible optimizations like early stopping.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your ability to identify binary search on answer space, implement feasibility checks correctly, and optimize code for efficiency.

Common Follow-ups

• What if packages can be shipped out of order? → Problem changes, might need different approach.
• How to handle very large weights or days? → Use 64-bit integers and efficient feasibility checks.

💡 These follow-ups test your understanding of problem constraints and ability to adapt your solution.

🔍

Pattern Recognition

When to Use

1) Problem asks to minimize or maximize a numeric answer. 2) The answer lies within a known numeric range. 3) You can check feasibility of a candidate answer efficiently. 4) Input array is not necessarily sorted or binary search on input doesn't apply.

Signature Phrases

minimum capacityship within dayscan we ship with capacity X

NOT This Pattern When

Problems that require binary search on sorted arrays or classic DP problems are different patterns.

Similar Problems

Split Array Largest Sum - similar binary search on max subarray sumKoko Eating Bananas - binary search on eating speedMinimum Time to Complete Trips - binary search on time

Practice

1. You are given an array of positive integers and a threshold value. You want to find the smallest integer divisor such that when each array element is divided by this divisor and rounded up, the sum of these results does not exceed the threshold. Which algorithmic approach guarantees finding this smallest divisor efficiently?

easy

A. Greedy approach that picks divisors based on local minimum sums without backtracking

B. Dynamic programming to explore all divisor combinations and sums

C. Binary search on the divisor value combined with a feasibility check function

D. Sorting the array and using two pointers to find the divisor

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the smallest divisor that satisfies a sum condition involving ceiling division, which is monotonic with respect to the divisor.

2. Step 2: Identify the suitable algorithmic pattern

   Binary search on the answer space (divisor values) combined with a helper feasibility function efficiently narrows down the smallest divisor by checking if a candidate divisor meets the threshold condition.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search exploits monotonicity of feasibility -> [OK]

Hint: Monotonic feasibility suggests binary search on answer space [OK]

Common Mistakes:

• Assuming greedy local choices yield global minimum divisor
• Trying DP which is inefficient and unnecessary here
• Using sorting and two pointers which don't apply to divisor search

2. You are given a sorted array that has been rotated at an unknown pivot and may contain duplicates. You need to determine if a target value exists in this array efficiently. Which approach best guarantees an optimal average-case runtime while correctly handling duplicates?

easy

A. Use a simple linear scan through the array to find the target.

B. Apply a modified binary search that skips duplicates from both ends before deciding which half to search.

C. Use a classic binary search assuming no duplicates and no rotation.

D. Apply a dynamic programming approach to track possible target positions.

Solution

1. Step 1: Understand problem constraints

   The array is rotated and contains duplicates, which breaks classic binary search assumptions.

2. Step 2: Identify approach handling duplicates and rotation

   Modified binary search that skips duplicates at both ends before deciding the sorted half ensures correctness and efficiency.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Duplicates cause ambiguity; skipping them resolves it [OK]

Hint: Skip duplicates at boundaries before binary search [OK]

Common Mistakes:

• Assuming classic binary search works with duplicates
• Using DP unnecessarily
• Relying on linear scan for efficiency

3. What is the time complexity of the optimized binary search solution for finding the k-th smallest number in an m x n multiplication table, where the counting function breaks early once count ≥ k?

medium

A. O(m * log(m * n))

B. O(m log(m * n))

C. O(log(m * n))

D. O(m * n log(m * n))

Solution

1. Step 1: Identify outer binary search iterations

   The binary search runs over the value range [1, m*n], so about O(log(m*n)) iterations.

2. Step 2: Analyze counting function complexity

   Counting iterates over m rows, each capped by min(n, x//i), but early break reduces average work. Worst case is O(m) per count.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(m * log(m * n)) [OK]

Hint: Counting is O(m), binary search O(log(m*n)) [OK]

Common Mistakes:

• Confusing n with m in complexity
• Assuming counting is O(m*n)

4. Identify the bug in the following modified code snippet for the Minimum Days to Make m Bouquets problem:

medium

A. The feasibility function does not reset flowers count correctly.

B. Binary search boundaries are incorrectly set from 0 instead of min bloom day.

C. The initial check for m * k > n is missing, causing unnecessary computation.

D. Early stopping in feasibility function is missing, causing slower runtime.

Solution

1. Step 1: Check initial conditions

   The code lacks the check if m * k > n, which means it's impossible to make required bouquets.

2. Step 2: Consequences of missing check

   Without this, the code runs unnecessary binary search and feasibility checks, possibly returning wrong answers or timing out.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding the initial impossible case check fixes the bug. [OK]

Hint: Always check if total flowers suffice before processing [OK]

Common Mistakes:

• Forgetting impossible case check
• Misresetting flowers count in feasibility

5. Suppose the array can contain negative numbers and the target can be any integer. Which modification to the optimal binary search algorithm is necessary to correctly handle this scenario?

hard

A. No modification needed; the existing algorithm works for any integers.

B. Replace all comparisons with absolute value comparisons to handle negatives.

C. Add explicit checks for negative values before deciding which half is sorted.

D. Use a linear scan instead since binary search assumptions break with negatives.

Solution

1. Step 1: Understand impact of negative numbers

   Negative numbers do not break rotation or duplicates but affect comparison logic when deciding sorted halves.

2. Step 2: Modify comparison logic

   Explicitly check and compare values considering negatives to correctly identify sorted half and target range.

3. Step 3: Reject naive absolute value or linear scan

   Absolute values distort order; linear scan is inefficient and unnecessary.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Comparisons must handle negatives explicitly [OK]

Hint: Adjust comparisons to handle negatives explicitly [OK]

Common Mistakes:

• Assuming negatives don't affect comparisons
• Using absolute values incorrectly
• Switching to linear scan unnecessarily