Crack the Backend

Problem Statement

You have weights[i] representing the weight of the i-th package. Ships carry packages in order; each ship has the same capacity cap. We need to ship all packages within days days (at most one ship per day). Return the minimum cap such that all packages can be shipped within days days.

Lower bound for cap is max(weights) (each package must fit). Upper bound is sum(weights) (one ship could take all). We binary search on cap. For a given cap, check if we can ship in <= days using a greedy simulation: fill the current ship until adding the next package would exceed cap, then start a new day.

Key Observations

Binary search on the answer: low = max(weights), high = sum(weights). For mid, define possible(mid): can we ship all packages in at most days days with capacity mid? Greedy: iterate packages, accumulate weight; when adding the next would exceed mid, start a new ship (new day). Count days; return true if days <= D.
If possible(mid) is true, any larger capacity also works; so we search for the minimum cap that works: if possible(mid), set high = mid (or answer = mid, high = mid - 1); else low = mid + 1. Return low (or the stored answer).

Approach

High-level: Binary search cap in [max(weights), sum(weights)]. For each mid, simulate: need = 1 day, cur = 0; for each weight w: if cur + w > mid then need++, cur = 0; cur += w. If need <= days, high = mid; else low = mid + 1. Return low.

Steps:

low = max(weights), high = sum(weights). While low < high: mid = low + (high - low) / 2. Compute need (number of days) with capacity mid (greedy). If need <= days, high = mid; else low = mid + 1.
Return low.

Implementation

Java

public int shipWithinDays(int[] weights, int days) {
    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;
        int need = 1, cur = 0;

        for (int w : weights) {
            if (cur + w > mid) { need++; cur = 0; }
            cur += w;
        }

        if (need <= days) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }

    return low;
}

Test Cases

Example 1

Input

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

Expected

15

Explanation

Min capacity 15.

Complexity Analysis

Time: O(n log(sum)).
Space: O(1).

Follow-ups

Split array largest sum (same idea).