The O(n) Club: Capacity to Ship Packages Within D Days — Goldilocks Goes Binary

The O(n) Club: Capacity to Ship Packages Within D Days — Goldilocks Goes Binary

⚡ TL;DR

Given a lineup of stubbornly ordered packages and a deadline (D days), you need to pick the smallest ship that doesn’t burst at the seams. Brute force means checking every possible capacity—hope you love O(n²) time. Instead, binary search the minimum ‘Goldilocks’ capacity. Here’s a Java snippet even your sleepiest brain can grok:

// Brute-force (please don't)
int min = maxWeight, max = sumWeights;
for (int cap = min; cap <= max; cap++) {
    if (canShip(weights, D, cap)) return cap;
}

🧠 How Devs Usually Mess This Up

Picture this: You see “D days” and arrays and immediately reach for your favorite partition or DP toolkit. Bad move! Here’s how most caffeine-deficient devs flub it:

• Reordering packages like they’re candy in a bowl. Sorry, logistics doesn’t work that way.
• Assuming each day magically gets an even load (spoiler: not how it works when you’re stuck with the input order).
• Confusing number of ships with days. If only port bureaucracy were that simple.

🔍 What’s Actually Going On

Imagine you’re a frazzled port manager with only one ship and too many packages. Each day, you load packages in order until the hull creaks, then race to dump cargo at the next port. Your goal: pick the smallest ship that survives D days. The trick? Use binary search—not on your input, but on the answer itself. Each guess says, “Is this ship big enough?” A greedy simulation steps through the packages; if you need more than D days, time to upgrade your ride. If not, maybe your giant ship is just showing off. Rinse, repeat.

🛠️ PseudoCode

• Find your search range:
  • Low = max(packages). Can’t use a ship smaller than the heaviest box—unless you want to invent teleportation.
  • High = sum(packages). Empty your wallet and do it in a day.
• Binary search that space:

  while (low < high) {
      int mid = (low + high) / 2;
      if (canShip(weights, D, mid)) {
          high = mid;
      } else {
          low = mid + 1;
      }
  }

  At the end, ‘low’ is your Goldilocks size: not too big, not too small.
• Greedy helper:
  • Walk through the packages, tracking today’s load. If one more box will send you to Davy Jones, start a new day.
  • If it takes more than D days, this ship is too puny.

  int days = 1, load = 0;
  for (int w : weights) {
      if (load + w > cap) {
          days++;
          load = 0;
      }
      load += w;
  }
  return days <= D;
  

💻 The Code

public int shipWithinDays(int[] weights, int D) {
    int low = 0, high = 0;
    for (int w : weights) {
        low = Math.max(low, w);
        high += w;
    }
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (canShip(weights, D, mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}
 private boolean canShip(int[] weights, int D, int cap) {
    int days = 1, load = 0;
    for (int w : weights) {
        if (load + w > cap) {
            days++;
            load = 0;
        }
        load += w;
        if (days > D) return false;
    }
    return true;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge Case: You started ‘low’ at zero or the wrong place? Hope you like infinite loops (pro tip: start at max(weights)).
• Dreaming of rearranging the array? Stick to the order or get TLE as punishment.
• Complexity: O(n log S), where S is total weight (your search space). It’s snappy… unless your ship is made of code spaghetti.

🧠 Interviewer Brain-Tattoo

“The only thing you can safely cut corners on is pizza—not binary search. Search the answer, not the problem.”