Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbinary-search-on-answer

Capacity To Ship Packages Within D Days

Problem (restated)

Packages must ship in order within days days. Find the least weight capacity of the ship that makes this possible.

Intuition

Feasibility is monotonic in capacity: if C works, C+1 works. Binary search the capacity.

Approaches

Binary search on capacity

Tested only

Time O(n log S)Space O(1)

Idea. lo = max(weights), hi = sum(weights). For mid capacity, greedy-count days needed.

Walkthrough. weights=[1,2,3,4,5,6,7,8,9,10], days=5 → answer 15.

Trade-offs. Same pattern as Koko; define a clear canShip(cap) predicate.

Solution

export function shipWithinDays(weights: number[], days: number): number {
  let lo = Math.max(...weights);
  let hi = weights.reduce((a, b) => a + b, 0);
  const ok = (cap: number) => {
    let d = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { d++; load = 0; }
      load += w;
    }
    return d <= days;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

export function shipWithinDays(weights: number[], days: number): number {
  let lo = Math.max(...weights);
  let hi = weights.reduce((a, b) => a + b, 0);
  const ok = (cap: number) => {
    let d = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { d++; load = 0; }
      load += w;
    }
    return d <= days;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Reflection

Which cue made you pick this pattern in under 90 seconds?
What input would break a wrong invariant?