What is the time and space complexity of Capacity To Ship Packages?

Time complexity: O(n log S) where S is sum of weights. Space complexity: O(1).

Capacity To Ship Packages

Med

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Capacity To Ship Packages

Approach

Binary search on ship capacity from max(weights) to sum(weights). For each candidate capacity, greedily load packages into consecutive days and count days needed. If it fits within d days, try smaller capacity.

Complexity Analysis

Time: O(n log S) where S is sum of weights
Space: O(1)

Pattern

Binary Search on Answer

Why It Works

If capacity C works, C+1 also works (monotonic). Search space is [max(weights), sum(weights)]. For each candidate, greedily assign packages to days.

Updated Feb 2026