1011. Capacity to Ship Packages Within D Days - Explanation

Description

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). It is not allowed to load weight more than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Example 1:

Input: weights = [2,4,6,1,3,10], days = 4

Output: 10

Explanation:
1st day: [2]
2nd day: [4,6]
3rd day: [1,3]
4th day: [10]

Example 2:

Input: weights = [1,2,3,4,5], days = 5

Output: 5

Explanation:
1st day: [1]
2nd day: [2]
3rd day: [3]
4th day: [4]
5th day: [5]

Example 3:

Input: weights = [1,5,4,4,2,3], days = 3

Output: 8

Explanation:
1st day = [1,5]
2nd day = [4,4]
3rd day = [2,3]

Constraints:

1 <= days, weights.length <= 50,000
1 <= weights[i] <= 500

Topics

Array Binary Search

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Search - Searching over a monotonic answer space to find optimal values
Greedy Simulation - Simulating a process with greedy decisions to validate a candidate answer
Problem Decomposition - Breaking down optimization problems into feasibility checks

1. Linear Search

Intuition

The minimum possible ship capacity must be at least as large as the heaviest package (otherwise that package could never be shipped). Starting from this minimum value, we can try each capacity one by one, simulating the shipping process to see if all packages can be delivered within the given number of days. The first capacity that works is our answer.

Algorithm

Initialize the result to the maximum weight in the array (the minimum possible capacity).
For the current capacity, simulate shipping by iterating through packages:
- Keep a running total of the current ship's load.
- When adding a package would exceed capacity, start a new ship.
If the number of ships used is within the allowed days, return the current capacity.
Otherwise, increment the capacity by 1 and repeat.

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        res = max(weights)
        while True:
            ships = 1
            cap = res
            for w in weights:
                if cap - w < 0:
                    ships += 1
                    cap = res
                cap -= w

            if ships <= days:
                return res

            res += 1

public class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int res = 0;
        for (int weight : weights) {
            res = Math.max(res, weight);
        }
        while (true) {
            int ships = 1;
            int cap = res;
            for (int weight : weights) {
                if (cap - weight < 0) {
                    ships++;
                    cap = res;
                }
                cap -= weight;
            }
            if (ships <= days) {
                return res;
            }
            res++;
        }
    }
}

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int res = *max_element(weights.begin(), weights.end());
        while (true) {
            int ships = 1, cap = res;
            for (int w : weights) {
                if (cap - w < 0) {
                    ships++;
                    cap = res;
                }
                cap -= w;
            }
            if (ships <= days) {
                return res;
            }
            res++;
        }
    }
};

class Solution {
    /**
     * @param {number[]} weights
     * @param {number} days
     * @return {number}
     */
    shipWithinDays(weights, days) {
        let res = Math.max(...weights);
        while (true) {
            let ships = 1,
                cap = res;
            for (let w of weights) {
                if (cap - w < 0) {
                    ships++;
                    cap = res;
                }
                cap -= w;
            }
            if (ships <= days) {
                return res;
            }
            res++;
        }
    }
}

public class Solution {
    public int ShipWithinDays(int[] weights, int days) {
        int res = weights.Max();
        while (true) {
            int ships = 1;
            int cap = res;
            foreach (int w in weights) {
                if (cap - w < 0) {
                    ships++;
                    cap = res;
                }
                cap -= w;
            }
            if (ships <= days) {
                return res;
            }
            res++;
        }
    }
}

func shipWithinDays(weights []int, days int) int {
    res := 0
    for _, w := range weights {
        if w > res {
            res = w
        }
    }

    for {
        ships := 1
        cap := res
        for _, w := range weights {
            if cap-w < 0 {
                ships++
                cap = res
            }
            cap -= w
        }
        if ships <= days {
            return res
        }
        res++
    }
}

class Solution {
    fun shipWithinDays(weights: IntArray, days: Int): Int {
        var res = weights.max()

        while (true) {
            var ships = 1
            var cap = res
            for (w in weights) {
                if (cap - w < 0) {
                    ships++
                    cap = res
                }
                cap -= w
            }
            if (ships <= days) {
                return res
            }
            res++
        }
    }
}

class Solution {
    func shipWithinDays(_ weights: [Int], _ days: Int) -> Int {
        var res = weights.max()!

        while true {
            var ships = 1
            var cap = res
            for w in weights {
                if cap - w < 0 {
                    ships += 1
                    cap = res
                }
                cap -= w
            }
            if ships <= days {
                return res
            }
            res += 1
        }
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Binary Search

Intuition

Instead of checking every capacity linearly, we can use binary search because the problem has a monotonic property: if a capacity works, any larger capacity will also work. The search space ranges from the maximum package weight (minimum valid capacity) to the sum of all weights (shipping everything in one day). For each mid-point capacity, we check if it allows shipping within the day limit and adjust our search accordingly.

Algorithm

Set the binary search range: left = max(weights), right = sum(weights).
While left <= right:
- Calculate mid = (left + right) / 2.
- Simulate shipping with capacity mid by greedily filling each day's ship.
- If we can ship within the allowed days, update the result and search the left half (r = mid - 1).
- Otherwise, search the right half (l = mid + 1).
Return the minimum valid capacity found.

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        l, r = max(weights), sum(weights)
        res = r

        def canShip(cap):
            ships, currCap = 1, cap
            for w in weights:
                if currCap - w < 0:
                    ships += 1
                    if ships > days:
                        return False
                    currCap = cap

                currCap -= w
            return True

        while l <= r:
            cap = (l + r) // 2
            if canShip(cap):
                res = min(res, cap)
                r = cap - 1
            else:
                l = cap + 1

        return res

public class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int l = 0, r = 0;
        for (int w : weights) {
            l = Math.max(l, w);
            r += w;
        }
        int res = r;

        while (l <= r) {
            int cap = (l + r) / 2;
            if (canShip(weights, days, cap)) {
                res = Math.min(res, cap);
                r = cap - 1;
            } else {
                l = cap + 1;
            }
        }
        return res;
    }

    private boolean canShip(int[] weights, int days, int cap) {
        int ships = 1, currCap = cap;
        for (int w : weights) {
            if (currCap - w < 0) {
                ships++;
                if (ships > days) {
                    return false;
                }
                currCap = cap;
            }
            currCap -= w;
        }
        return true;
    }
}

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int l = *max_element(weights.begin(), weights.end());
        int r = accumulate(weights.begin(), weights.end(), 0);
        int res = r;

        while (l <= r) {
            int cap = (l + r) / 2;
            if (canShip(weights, days, cap)) {
                res = min(res, cap);
                r = cap - 1;
            } else {
                l = cap + 1;
            }
        }
        return res;
    }

private:
    bool canShip(const vector<int>& weights, int days, int cap) {
        int ships = 1, currCap = cap;
        for (int w : weights) {
            if (currCap - w < 0) {
                ships++;
                if (ships > days) {
                    return false;
                }
                currCap = cap;
            }
            currCap -= w;
        }
        return true;
    }
};

class Solution {
    /**
     * @param {number[]} weights
     * @param {number} days
     * @return {number}
     */
    shipWithinDays(weights, days) {
        let l = Math.max(...weights);
        let r = weights.reduce((a, b) => a + b, 0);
        let res = r;

        const canShip = (cap) => {
            let ships = 1,
                currCap = cap;
            for (const w of weights) {
                if (currCap - w < 0) {
                    ships++;
                    if (ships > days) {
                        return false;
                    }
                    currCap = cap;
                }
                currCap -= w;
            }
            return true;
        };

        while (l <= r) {
            const cap = Math.floor((l + r) / 2);
            if (canShip(cap)) {
                res = Math.min(res, cap);
                r = cap - 1;
            } else {
                l = cap + 1;
            }
        }

        return res;
    }
}

public class Solution {
    public int ShipWithinDays(int[] weights, int days) {
        int l = weights.Max();
        int r = weights.Sum();
        int res = r;

        bool CanShip(int cap) {
            int ships = 1;
            int currCap = cap;

            foreach (int w in weights) {
                if (currCap - w < 0) {
                    ships++;
                    if (ships > days) return false;
                    currCap = cap;
                }
                currCap -= w;
            }

            return true;
        }

        while (l <= r) {
            int cap = (l + r) / 2;
            if (CanShip(cap)) {
                res = Math.Min(res, cap);
                r = cap - 1;
            } else {
                l = cap + 1;
            }
        }

        return res;
    }
}

func shipWithinDays(weights []int, days int) int {
    l, r := 0, 0
    for _, w := range weights {
        if w > l {
            l = w
        }
        r += w
    }
    res := r

    canShip := func(cap int) bool {
        ships, currCap := 1, cap
        for _, w := range weights {
            if currCap-w < 0 {
                ships++
                if ships > days {
                    return false
                }
                currCap = cap
            }
            currCap -= w
        }
        return true
    }

    for l <= r {
        cap := (l + r) / 2
        if canShip(cap) {
            if cap < res {
                res = cap
            }
            r = cap - 1
        } else {
            l = cap + 1
        }
    }

    return res
}

class Solution {
    fun shipWithinDays(weights: IntArray, days: Int): Int {
        var l = weights.max()
        var r = weights.sum()
        var res = r

        fun canShip(cap: Int): Boolean {
            var ships = 1
            var currCap = cap
            for (w in weights) {
                if (currCap - w < 0) {
                    ships++
                    if (ships > days) return false
                    currCap = cap
                }
                currCap -= w
            }
            return true
        }

        while (l <= r) {
            val cap = (l + r) / 2
            if (canShip(cap)) {
                res = minOf(res, cap)
                r = cap - 1
            } else {
                l = cap + 1
            }
        }

        return res
    }
}

class Solution {
    func shipWithinDays(_ weights: [Int], _ days: Int) -> Int {
        var l = weights.max()!
        var r = weights.reduce(0, +)
        var res = r

        func canShip(_ cap: Int) -> Bool {
            var ships = 1
            var currCap = cap
            for w in weights {
                if currCap - w < 0 {
                    ships += 1
                    if ships > days { return false }
                    currCap = cap
                }
                currCap -= w
            }
            return true
        }

        while l <= r {
            let cap = (l + r) / 2
            if canShip(cap) {
                res = min(res, cap)
                r = cap - 1
            } else {
                l = cap + 1
            }
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$

Common Pitfalls

Wrong Binary Search Bounds

The minimum capacity must be at least max(weights) (to ship the heaviest package), and the maximum is sum(weights) (ship everything in one day). Starting from 0 or 1 leads to invalid states where some packages cannot be shipped.

# Wrong: minimum capacity too low
l, r = 1, sum(weights)  # Should be: l = max(weights)

Miscounting Days in Simulation

A common mistake is not counting the first day or incrementing the day counter at the wrong time. The ship starts with capacity available on day 1, and a new day begins when the current package cannot fit.

Using Incorrect Binary Search Condition

This is a "find minimum satisfying condition" problem. When the capacity works, you should search left (r = mid - 1) to find smaller valid capacities. Searching right instead returns a suboptimal answer.