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 <= maxWeightThe #1687 Delivering Boxes from Storage to Ports problem is a challenging logistics optimization task that combines constraints on box count, weight, and port visits. A common strategy is to use dynamic programming where dp[i] represents the minimum number of trips needed to deliver the first i boxes.
To efficiently compute transitions, we maintain a sliding window of valid boxes that respect the maximum box and weight limits. Prefix sums help quickly track cumulative weights and detect when constraints are exceeded. Additionally, we track port changes to determine the number of port visits within a delivery batch.
To optimize the DP transition, a monotonic queue (or deque) can be used. It maintains candidate indices that minimize the transition cost, allowing us to update states in amortized constant time. This avoids the quadratic brute-force scan of previous states.
With these optimizations, the algorithm runs in O(n) time with linear auxiliary space, making it scalable for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Prefix Sum and Monotonic Queue | O(n) | O(n) |
| Naive Dynamic Programming | O(n^2) | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Try to think of the most basic dp which is n^2 now optimize it
Think of any range query data structure to optimize
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems similar to #1687 often appear in FAANG-style interviews because they combine dynamic programming with data structure optimization. They test a candidate's ability to reduce time complexity using advanced techniques like monotonic queues.
Prefix sums allow quick calculation of cumulative weights and other metrics across a range of boxes. This makes it easy to verify whether a group of boxes satisfies the maximum weight constraint without recomputing sums repeatedly.
A monotonic queue (deque) is particularly effective for this problem. It helps efficiently maintain candidate DP states and ensures transitions are computed in amortized constant time.
The optimal approach uses dynamic programming combined with prefix sums and a monotonic queue. This structure helps maintain the best previous states while respecting box count and weight constraints, reducing the complexity to linear time.