Watch 6 video solutions for Delivering Boxes from Storage to Ports, a hard level problem involving Array, Dynamic Programming, Segment Tree. This walkthrough by Happy Coding has 2,451 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have the task of delivering some boxes from storage to their ports using only one ship. However, this ship has a limit on the number of boxes and the total weight that it can carry.
You are given an array boxes, where boxes[i] = [portsi, weighti], and three integers portsCount, maxBoxes, and maxWeight.
portsi is the port where you need to deliver the ith box and weightsi is the weight of the ith box.portsCount is the number of ports.maxBoxes and maxWeight are the respective box and weight limits of the ship.The boxes need to be delivered in the order they are given. The ship will follow these steps:
boxes queue, not violating the maxBoxes and maxWeight constraints.The ship must end at storage after all the boxes have been delivered.
Return the minimum number of trips the ship needs to make to deliver all boxes to their respective ports.
Example 1:
Input: boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3 Output: 4 Explanation: The optimal strategy is as follows: - The ship takes all the boxes in the queue, goes to port 1, then port 2, then port 1 again, then returns to storage. 4 trips. So the total number of trips is 4. Note that the first and third boxes cannot be delivered together because the boxes need to be delivered in order (i.e. the second box needs to be delivered at port 2 before the third box).
Example 2:
Input: boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6 Output: 6 Explanation: The optimal strategy is as follows: - The ship takes the first box, goes to port 1, then returns to storage. 2 trips. - The ship takes the second, third and fourth boxes, goes to port 3, then returns to storage. 2 trips. - The ship takes the fifth box, goes to port 2, then returns to storage. 2 trips. So the total number of trips is 2 + 2 + 2 = 6.
Example 3:
Input: boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7 Output: 6 Explanation: The optimal strategy is as follows: - The ship takes the first and second boxes, goes to port 1, then returns to storage. 2 trips. - The ship takes the third and fourth boxes, goes to port 2, then returns to storage. 2 trips. - The ship takes the fifth and sixth boxes, goes to port 3, then returns to storage. 2 trips. So the total number of trips is 2 + 2 + 2 = 6.
Constraints:
1 <= boxes.length <= 1051 <= portsCount, maxBoxes, maxWeight <= 1051 <= portsi <= portsCount1 <= weightsi <= maxWeightProblem Overview: You are given a sequence of boxes where each box has a destination port and weight. A ship loads boxes in order from storage, but each trip is limited by maxBoxes and maxWeight. The goal is to minimize the total number of trips required to deliver all boxes while accounting for port switches during a trip.
Approach 1: Greedy Window Simulation (O(n))
This method simulates loading boxes into the ship using a sliding window. Start from the current box and greedily add as many boxes as possible while respecting maxBoxes and maxWeight. Track how many times the destination port changes inside the window because every change adds an additional port visit. Prefix arrays help maintain port-change counts efficiently. When the constraints break, move the window start forward and update weight and port transitions. This approach uses arrays and prefix sums to track transitions and compute trip costs quickly. Time complexity is O(n) since each box enters and leaves the window once, and space complexity is O(n) for prefix tracking.
Approach 2: Dynamic Programming with Monotonic Queue (O(n))
The optimal solution models the problem as dp[i]: the minimum trips needed to deliver the first i boxes. For every ending position i, you determine the earliest valid start j that satisfies both box-count and weight constraints. The trip cost from j to i equals the number of port transitions plus the final return trip. Prefix arrays store port-change counts, allowing the cost of any segment to be computed in constant time. A monotonic queue maintains candidate indices that minimize the DP transition value dp[j] - portChanges[j]. As the window slides forward, outdated indices are removed and the best candidate remains at the front. This converts a naive O(n²) DP transition into an O(n) algorithm with O(n) space.
Recommended for interviews: The dynamic programming solution with a monotonic queue is the approach most interviewers expect. It demonstrates your ability to combine dynamic programming with sliding-window constraints and prefix calculations. A greedy simulation helps build intuition about port transitions and shipment grouping, but the DP formulation shows stronger algorithmic depth and optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Sliding Window | O(n) | O(n) | Good for understanding shipment grouping and port transitions before introducing DP. |
| Dynamic Programming + Monotonic Queue | O(n) | O(n) | Optimal solution for large inputs; converts quadratic DP into linear time. |