coding_challengeshigh priority

Ship Packages in D Days — Binary Search on Answer

📋 The problem — read this first
A conveyor belt has packages that must ship within `days` days. The i-th
package weighs weights[i]. Each day you load the ship with packages IN THE
GIVEN ORDER without exceeding its capacity. Find the LEAST ship capacity so
that everything ships within `days` days.  (LeetCode 1011)

Key idea: the answer is monotonic — if capacity C works, every capacity > C
also works — so binary-search the capacity and test feasibility (how many days
a given capacity needs).

Example:
  Input:  weights = [1,2,3,4,5,6,7,8,9,10],  days = 5
  Output: 15
    With capacity 15 the loads are [1,2,3,4,5] [6,7] [8] [9] [10] = 5 days.
    Capacity 14 needs 6 days, so 15 is the minimum.
💡 The solution — step through it
1 / 5
Spot the pattern — binary search on the ANSWERweights[]12345678910Three signals → search the answer spaceGoal: MINIMIZE the ship capacityfeasible(cap): O(n) — fits in D days?Monotonic: bigger cap → never more days⇒ binary search the capacity, not the array
example.cpp
1// LeetCode 1011 — Capacity To Ship Packages Within D Days.
2// Ship weights[] IN ORDER; minimize the daily ship capacity so all
3// packages ship within 'days' days.
4int shipWithinDays(std::vector<int>& w, int days) {
5    int lo = *std::max_element(w.begin(), w.end());  // >= heaviest box
6    int hi = std::accumulate(w.begin(), w.end(), 0);  // all in one day
7 
8    auto daysNeeded = [&](int cap) {        // feasibility check
9        int d = 1, load = 0;
10        for (int x : w) {
11            if (load + x > cap) { ++d; load = 0; }  // new day
12            load += x;
13        }
14        return d;
15    };
16 
17    while (lo < hi) {                       // find MIN feasible cap
18        int mid = lo + (hi - lo) / 2;
19        if (daysNeeded(mid) <= days) hi = mid;     // feasible -> shrink
20        else                          lo = mid + 1; // infeasible -> grow
21    }
22    return lo;                              // lo == hi == answer
23}

Spot the pattern — binary search on the ANSWER

You're asked to MINIMIZE the daily capacity. Given a candidate capacity you can CHECK in O(n) whether everything ships within D days, and that check is MONOTONIC: a bigger capacity never needs more days. Minimize + linear feasibility + monotonic ⇒ binary-search the answer, not the array.

Tap ▶ to play · tap the dots or Next → to step

← Previous
Search in a Rotated Sorted Array
Next →
Burn the Binary Tree from a Target Node