🚀 Try This Problem First!

Before reading the solution, attempt it yourself on LeetCode — you'll retain the concept far better.

🔗 Problem Link: https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

1. Understanding the Problem

You have a conveyor belt carrying N packages, each with a given weight. A ship must transport all of them within at most D days. Every day, you load packages in order (no rearranging allowed), and you cannot exceed the ship's weight capacity in a single day.

Goal: Find the minimum weight capacity of the ship such that all packages are delivered within D days.

Constraints:

1. 1 ≤ days ≤ weights.length ≤ 5 × 10⁴
2. 1 ≤ weights[i] ≤ 500

2. Two Key Observations (Before Writing a Single Line of Code)

Before jumping to code, anchor yourself with these two facts:

Minimum possible capacity: The ship must at least be able to carry the single heaviest package. If it can't, that package can never be shipped. So:

low = max(weights)

Maximum possible capacity: If the ship can carry everything at once, it finishes in 1 day — always valid. So:

high = sum(weights)

Our answer lies somewhere in the range [max(weights), sum(weights)]. This is the classic setup for Binary Search on the Answer.

3. Intuition — Why Binary Search?

Ask yourself: what happens as ship capacity increases?

The number of days needed decreases or stays the same. This is a monotonic relationship — and monotonicity is the green flag for Binary Search.

Instead of checking every capacity from 1 to sum(weights) (which is huge), we binary search over the capacity space and for each candidate capacity mid, we ask:

"Can all packages be shipped in ≤ D days with this capacity?"

This feasibility check runs in O(N) using a greedy simulation, making the whole approach O(N log(sum(weights))).

4. The Feasibility Check — Greedy Loading

Given a capacity mid, simulate loading the ship greedily:

1. Keep adding packages to today's load.
2. The moment adding the next package would exceed mid, start a new day and reset the current load to that package.
3. Count total days used.
4. If days used ≤ D, capacity mid is feasible.

5. Binary Search Strategy

1. If canShip(mid) is true → mid might be the answer, but try smaller. Set ans = mid, high = mid - 1.
2. If canShip(mid) is false → capacity is too small, increase it. Set low = mid + 1.

6. Dry Run — Example 1

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

1. low = 10 (max weight), high = 55 (sum of weights)

Output: 15 ✅

7. The Code Implementation

8. Code Walkthrough — Step by Step

Step 1 — Setting bounds: We iterate through the weights array once to compute low = max(weights) and high = sum(weights). These are our binary search boundaries.

Step 2 — Binary Search loop: We pick mid = low + (high - low) / 2 (safe overflow-free midpoint). We check if capacity mid can ship all packages in ≤ D days.

Step 3 — Feasibility helper (canShip): We simulate a greedy day-by-day loading. We start with daysNeeded = 1 and currentLoad = 0. For each package, if it fits in today's load, we add it. If not, we start a new day. The key line is:

Step 4 — Narrowing the search: If feasible → ans = mid, high = mid - 1 (try smaller). If not feasible → low = mid + 1 (try larger).

9. Common Mistakes to Avoid

Mistake 1 — Wrong lower bound: Using low = 1 instead of low = max(weights) works but is far slower since you binary search over a much larger range unnecessarily.

Mistake 2 — Wrong condition in canShip: The return should be daysNeeded <= days (not < days). If days needed equals D, it's still valid.

Mistake 3 — Off-by-one in greedy loading: When a package doesn't fit, you start a new day with that package as the first item: currentLoad = arr[i]. Do NOT set currentLoad = 0 — that package must still be accounted for.

Mistake 4 — Integer overflow in midpoint: Always use mid = low + (high - low) / 2 instead of (low + high) / 2 to avoid overflow when low and high are large.

10. Complexity Analysis

Time Complexity: O(N × log(sum(weights)))

1. Binary search runs over the range [max(weights), sum(weights)], which has at most sum(weights) ≈ 500 × 50000 = 25,000,000 values → about log₂(25,000,000) ≈ 25 iterations.
2. Each iteration calls canShip which is O(N).
3. Total: O(N log S) where S = sum(weights).

Space Complexity: O(1)

1. No extra data structures. Only a handful of integer variables are used.

11. Similar Problems (Same Pattern — Binary Search on Answer)

Once you understand this pattern, the following problems become very similar:

1. LeetCode 410 — Split Array Largest Sum
2. LeetCode 875 — Koko Eating Bananas [ Blog is also avaliable on this - Read Now ]
3. LeetCode 1283 — Find the Smallest Divisor Given a Threshold
4. LeetCode 2064 — Minimized Maximum of Products Distributed to Any Store

All of these follow the same template: define a feasibility check, identify a monotonic answer space, and binary search over it.

12. Key Takeaways

✅ When you see "find the minimum/maximum value such that a condition holds" — think Binary Search on the Answer.

✅ The lower bound of the search space is the most constrained valid value (max weight here).

✅ The upper bound is the least constrained valid value (total weight here).

✅ The feasibility check must be O(N) or better to keep the overall complexity efficient.

✅ Greedy loading (pack as much as possible each day) is optimal here since packages must go in order.

Happy Coding! If this helped you, share it with a friend who's grinding LeetCode. 🚀