What is the brute force approach and complexity for Capacity To Ship Packages Within D Days?

Try capacity max, max+1, … and return the first that fits in `days` days with time complexity O((S − M) · N) and space complexity O(1).

What is the optimal approach and complexity for Capacity To Ship Packages Within D Days?

Binary search the range [max, sum]; test each guess with a greedy day count with optimal time complexity O(N log S) and space complexity O(1).

How do you identify the pattern for Capacity To Ship Packages Within D Days?

Look for key signals in the prompt: "least weight capacity" indicates "Minimum X such that it is possible" → binary search on the answer X.; "in the order given" indicates No reordering. For a fixed capacity, the only choice is where each day ends → a left-to-right greedy fill.; "within days days" indicates The check is "days needed ≤ days". A bigger ship never needs more days → monotonic..

Capacity To Ship Packages Within D Days

Medium·LeetCode #1011 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

Packages sit on a conveyor belt in a fixed order. Package i weighs weights[i]. They must all be shipped from one port to another within days days.

Each day the ship is loaded with packages in belt order, starting from the next unshipped package. The total weight loaded on one day can't go over the ship's capacity. You can't skip a package or change the order.

Return the smallest ship capacity that ships every package within days days.

Input

An integer array weights and an integer days.

Output

One integer: the minimum ship capacity.

Example 1

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

Output: 15

With capacity 15 the days are [1,2,3,4,5], [6,7], [8], [9], [10]. With capacity 14 you need 6 days.

Example 2

Input: weights = [3, 2, 2, 4, 1, 4], days = 3

Output: 6

With capacity 6 the days are [3,2], [2,4], [1,4].

Example 3

Input: weights = [1, 2, 3, 1, 1], days = 4

Output: 3

With capacity 3 the days are [1,2], [3], [1,1]. That is only 3 days, which is allowed (at most 4).

Constraints

• 1 ≤ days ≤ weights.length ≤ 5 · 10^4
• 1 ≤ weights[i] ≤ 500

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“least weight capacity”

→ "Minimum X such that it is possible" → binary search on the answer X.

“in the order given”

→ No reordering. For a fixed capacity, the only choice is where each day ends → a left-to-right greedy fill.

“within days days”

→ The check is "days needed ≤ days". A bigger ship never needs more days → monotonic.

Approach Complexity Ladder

Brute Force — try every capacity from max upwardO((S − M) · N)O(1)

Try capacity max, max+1, … and return the first that fits in `days` days

Optimal — binary search on the capacityO(N log S)O(1)

Binary search the range [max, sum]; test each guess with a greedy day count

Brute Force Intuition

The answer is at least the heaviest package. So try capacities max, max + 1, max + 2, …. For each one, load the ship greedily and count the days. The first capacity that needs at most days days is the answer.

Recognition rule for this sub-pattern:

"Minimum capacity / speed / days such that it is possible." Guess an answer, check feasibility greedily, shrink the range.

Remember this · Binary Search

Trigger

Sorted data, "minimum X such that…", "maximum X such that…", rotated arrays, answers that are monotonic (if X works, X+1 also works).

Think

Is there a yes/no question whose answers look like NNNNYYYY? Then binary search for the first Y.

Key question

What is my check function, and is it monotonic?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Order Book Price Level Matching

std::lower_bound lookup in sorted price ticks for limit orders.

Explore Track

C++ Internals

CPU Branch Prediction & Cache Efficiency

Branch mispredictions in binary search and branchless mid-point arithmetic.

Explore Track

Koko Eating Bananas Minimum Number of Days to Make m Bouquets