DSA sheet · Binary Search · Binary search on answer

Capacity to Ship Packages Within D Days

The second problem of the binary search on answer pattern. The input array happens to be sorted in the example, and the teacher warns us not to be fooled by that: we don't search the array at all. We search over the possible ship capacities. The new things in this video are: how to prove the lower limit (it is max(weights), not 1), how to prove the upper limit (sum(weights)), and how to write the "how many days?" counter correctly, including two small bugs she makes and fixes while dry-running it.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: try every capacity from max to sum
• Part B · Optimal: binary search on the capacity
• Part C · Revision page

Part 0 · Before starting

Why binary search works at all

Binary search needs a yes/no question whose answers are arranged as all "no" first, then all "yes" (or the other way round), switching only once. Such a question is called monotonic. Then checking the middle tells us which half can't hold the switch point, and we drop that half. A sorted array is one example; a sorted range of numbers we choose is another.

low, high, mid

• low / high: the smallest / biggest value still in the running.
• mid: the value in the middle that we test now.
• Loop while low <= high, so that when only one value is left, it still gets tested.

Why mid = low + (high - low) // 2?

The teacher points out that the way we compute mid depends on the constraints. In Java/C++, (low + high) / 2 can overflow when low and high are both large: the sum goes past the int limit (about 2.1 × 10⁹) and becomes garbage. low + (high - low) / 2 never builds a number bigger than high, so it's safe. Python integers never overflow, so either form works in Python; we keep the safe form as a habit.

The pattern: binary search on answer

1. Answer range: decide the smallest answer that could possibly work (low) and a value that surely works (high).
2. Check function: check(x) = "if the answer were x, is it possible?" → True / False.
3. Monotonic: here, a ship that can carry more never needs more days. So if capacity x works, every bigger capacity also works: no no no yes yes yes.
4. Which side to keep: we want the minimum capacity = the first yes. Yes at mid → save mid, go left. No at mid → go right.

capacities:  low ......................................... high
check(x):     no   no   no   no  YES  YES  YES  YES  YES
                                 ^
                        the first YES = least capacity

Part A · Brute force: try every capacity from max to sum

LeetCode 1011

1The question in simple words

Packages sit on a conveyor belt in a fixed order. Package i weighs weights[i]. Every day, we load the ship with packages from the front of the belt, in order, as long as the total stays within the ship's capacity (the most weight it can carry in one trip). Then the ship leaves, and the next day we continue from where we stopped.

Find the least capacity so that all packages are shipped within days days.

Why 15? With capacity 15:

5 days ✓, and no smaller capacity manages it in 5 days.

A smaller illustration she uses first: with capacity 5, you can take 1 and 2 (total 3), but not 3 as well (that makes 6 > 5). Next trip, 3 alone, because 3 + 4 = 7 > 5.

2What the constraints tell us

• 1 <= days <= weights.length <= 5 × 10⁴ → at least one package, and days never exceeds the number of packages.
• 1 <= weights[i] <= 500 → small weights. The biggest possible total is 5 × 10⁴ × 500 = 2.5 × 10⁷, which fits easily in an int. So no overflow worry this time.
• The teacher's reason for always reading constraints in binary search: they tell us what low and high can be, and whether computing mid can overflow.

3Intuition

We are asked for a capacity, a number we assume ourselves, not something inside the array. So the plan is: guess a capacity, simulate the belt, count the days. If it takes too many days, the ship is too small; try a bigger one. Start from the smallest sensible capacity and go up. The first capacity that fits in days is the least.

4Building the logic from examples

The lower limit: why not start at 1 kg?

Try a 1 kg ship. Day 1 it takes the 1. Can it take 2 as well? No (1 + 2 = 3 > 1). Day 2: can it take the 2 kg package at all? No, never, the package alone is heavier than the ship. Same for 3, 4, … 10. With 2 kg the 3…10 packages can never go. With 5 kg, 6…10 can never go. Even 9 kg can't carry the 10.

So whatever the days, the ship must at least be able to lift the heaviest single package. Anything less is not even a candidate.

Is low itself the answer? Try capacity 10

• Day 1: 1 + 2 + 3 + 4 = 10, full.
• Day 2: 5. Adding 6 would make 11 > 10. The ship still has 5 kg free, but it can't skip ahead: packages leave in belt order. (Even if a 1 kg package were further down the belt, we couldn't jump to it.)
• Day 3: 6. Day 4: 7. Day 5: 8. Day 6: 9. Day 7: 10.

7 days > 5 days → not possible. Should we make the ship bigger or smaller? A smaller ship takes more days, so we need a bigger one. On the number line of capacities, from a capacity that fails, we move right.

The upper limit: why sum(weights)?

The teacher builds this from the constraint "days can be as small as 1":

• One package of 5 kg, days = 1 → the ship needs 5.
• One package of 15 kg, days = 1 → 15. (Here it equals the max too, so is the answer always the max? No…)
• Packages 2 kg and 7 kg, days = 1 → a 7 kg ship can't take both in one trip. You need 9 = 2 + 7.
• Packages 1…10, days = 1 → everything must go in a single trip: 55 = the whole sum.

A ship of capacity sum(weights) can always ship everything in 1 day, and days ≥ 1. So it always works, and going higher is pointless.

Writing the day counter (the heart of the problem)

The teacher builds canShip(weights, days, capacity) while dry-running capacity 15. We keep two variables: total (weight loaded on today's ship) and d (days used).

1. Take packages one by one and add them to total: 1, 3, 6, 10, 15.
2. Next is 6: 15 + 6 = 21 > 15. This package must go on a new day, so d goes up by one.
3. And today's load must be reset.

Continuing: day 2 starts with 6, then 6 + 7 = 13, then 13 + 8 = 21 > 15 → new day, total = 8. 8 + 9 = 17 > 15 → new day, total = 9. 9 + 10 = 19 > 15 → new day, total = 10. The loop ends.

Finally: return d <= days. Using fewer days than allowed is also fine.

5Approach steps

1. low = max(weights), high = sum(weights).
2. For each capacity cap from low to high: if canShip(cap), return cap.
3. canShip: d = 1, total = 0. For each w: if total + w > cap → d += 1, total = w; else total += w. Return d ≤ days.

6Code (Python)

class Solution:
    def shipWithinDays(self, weights, days):
        low = max(weights)                 # must lift the heaviest package
        high = sum(weights)                # ships everything in 1 day
        for cap in range(low, high + 1):
            if self.canShip(weights, days, cap):
                return cap                 # first that works = least
        return high

    def canShip(self, weights, days, cap):
        d = 1                              # we are on day 1
        total = 0                          # weight on today's ship
        for w in weights:
            if total + w > cap:            # w doesn't fit today
                d += 1                     # start a new day...
                total = w                  # ...with w on board (not 0!)
            else:
                total += w
        return d <= days

7Code line by line

8Dry run

weights = 1…10, days = 5. Range [10, 55].

capacity :  10  11  12  13  14  15  16  17  ...  55
days     :   7   6   6   6   6   5   5   4  ...   1
<= 5 ?   :  no  no  no  no  no YES YES YES ... YES
                                ^ first YES = 15

9Complexity & remember

• The outer loop can run sum − max times. Worst case: 5 × 10⁴ packages of 500 each → sum = 2.5 × 10⁷.
• Each try walks all 5 × 10⁴ packages. It's a nested loop, so we multiply: 2.5 × 10⁷ × 5 × 10⁴ ≈ 10¹² → TLE (she submits it and gets TLE, as expected).
• Space O(1).

Part B · Optimal: binary search on the capacity

1The question

Same as Part A. Same range, same canShip. Only the outer loop changes.

2Constraints

The range [max, sum] can be up to 2.5 × 10⁷ wide. Halving it needs only about log₂(2.5 × 10⁷) ≈ 25 steps.

3Intuition

The capacities max … sum are whole numbers on a number line, so they're sorted. And "can ship in time?" is no…no yes…yes along that line. So instead of trying them one by one, test the middle capacity and drop half the line. The inner loop (the belt simulation) can't be skipped, since we must look at every package to count the days.

4Building the decisions

• canShip(mid) is True: mid is a valid capacity and might be the least. Save it (ans = mid). A smaller one might also work, so search the left: high = mid - 1.
• canShip(mid) is False: mid is too small, and so is everything below it. Search the right: low = mid + 1.

She starts ans at 0. That's fine, because sum(weights) always works, so ans is always overwritten at least once.

5Approach steps

1. low = max(weights), high = sum(weights), ans = 0.
2. While low <= high: mid = low + (high - low) // 2 (the capacity to test).
3. If canShip(mid): ans = mid, high = mid - 1.
4. Else: low = mid + 1.
5. Return ans.

6Code (Python)

class Solution:
    def shipWithinDays(self, weights, days):
        low = max(weights)
        high = sum(weights)
        ans = 0
        while low <= high:
            mid = low + (high - low) // 2      # mid = capacity to test
            if self.canShip(weights, days, mid):
                ans = mid                      # works: remember it
                high = mid - 1                 # try a smaller ship
            else:
                low = mid + 1                  # too small: bigger ship
        return ans

    def canShip(self, weights, days, cap):
        d = 1
        total = 0
        for w in weights:
            if total + w > cap:
                d += 1
                total = w
            else:
                total += w
        return d <= days

7Code line by line

8Dry run (hand table)

weights = 1…10, days = 5. low = 10, high = 55.

The range of capacities shrinking (yellow = mid, grey = gone). Only the interesting part 10 … 20 is drawn:

9Complexity & remember

• Time O(n × log(sum − max)): about 25 halvings × 5 × 10⁴ packages ≈ 1.25 × 10⁶ → passes.
• Space O(1).

Part C · Revision page

s = Solution()
print(s.shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))   # 15
print(s.shipWithinDays([3, 2, 2, 4, 1, 4], 3))                # 6
print(s.shipWithinDays([1, 2, 3, 1, 1], 4))                   # 3
print(s.shipWithinDays([2, 7], 1))                            # 9
print(s.shipWithinDays([10], 1))                              # 10

Based on this video: Capacity to Ship Packages Within D Days | Binary Search on Answer