#1687

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Delivering Boxes from Storage to Ports

Optimize the minimum number of trips to deliver boxes to ports under strict ship constraints using dynamic programming transitions.

array dynamic programming segment tree queue heap priority queue

Problem Statement

You have a ship that must deliver a sequence of boxes from storage to their designated ports. Each box has a weight and a target port. The ship can carry at most maxBoxes boxes and cannot exceed maxWeight in total weight. Boxes must be delivered in the given order, and after visiting the last port for a batch, the ship returns to storage.

Given an array boxes where boxes[i] = [port_i, weight_i], and integers portsCount, maxBoxes, and maxWeight, determine the minimum number of trips needed to deliver all boxes to their respective ports. The ship follows a strict sequence: load boxes respecting capacity limits, deliver to each distinct port in order, and return to storage before the next batch.

Examples

Example 1

Input: boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3

Output: 4

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

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

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 <= 105
1 <= portsCount, maxBoxes, maxWeight <= 105
1 <= portsi <= portsCount
1 <= weightsi <= maxWeight

Solution Approach

Basic DP Formulation

Define dp[i] as the minimum trips to deliver the first i boxes. Iterate over all possible previous batch endpoints j < i to calculate dp[i] = min(dp[j] + trips_for_batch(j+1, i)). Compute trips_for_batch by counting port changes plus return trip to storage. This naive approach is O(n^2) and sets the foundation for optimizations.

Prefix Sums and Port Change Tracking

Precompute prefix sums for weights and count port changes between consecutive boxes. This allows constant-time evaluation of whether a batch from j+1 to i exceeds maxBoxes or maxWeight. Also quickly calculate extra trips for port switches, reducing redundant computation in the DP updates.

Monotonic Queue Optimization

Use a monotonic queue to maintain candidate dp[j] indices where j < i. This exploits the fact that dp values only increase with i and invalid batch start points can be removed. By efficiently maintaining the queue and applying the constraints, we reduce the DP complexity from O(n^2) to near O(n), optimizing for large input sizes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the optimization: naive DP is O(n^2), prefix sums reduce some overhead, and monotonic queue optimization approaches O(n). Space complexity is O(n) for storing dp array and prefix sums.

What Interviewers Usually Probe

Expect discussion of state transition dynamic programming patterns with sequential dependencies.
Look for handling multiple constraints: maxBoxes, maxWeight, and ordered delivery.
Interest in reducing naive O(n^2) DP via prefix sums or monotonic structures.

Common Pitfalls or Variants

Common pitfalls

Failing to respect the delivery order of boxes when forming DP batches.
Overlooking the cumulative weight and box limits when computing each batch.
Incorrectly counting trips when consecutive boxes go to the same port.

Follow-up variants

Allow boxes to be delivered out of order, which changes DP formulation significantly.
Introduce variable ship capacity per trip, requiring dynamic adjustment in DP batch evaluation.
Optimize for cases where portCount is very large relative to boxes, leveraging sparse updates.

FAQ

What pattern is used in Delivering Boxes from Storage to Ports?

The problem uses state transition dynamic programming with sequential dependency and batch evaluation under constraints.

How do I handle maxBoxes and maxWeight constraints?

Precompute prefix sums for box counts and weights to quickly check if a batch exceeds limits before updating DP.

Why is monotonic queue useful in this problem?

It efficiently maintains candidate batch starting points for DP, removing invalid options and reducing overall complexity.

Can boxes be delivered out of order?

No, the boxes must be delivered in order, which is essential for the DP transitions to be correct.

What is the time complexity after optimization?

After prefix sums and monotonic queue optimization, the DP approaches O(n) time complexity with O(n) space.

terminal

Solution

Solution 1: Dynamic Programming + Monotonic Queue Optimization

We define $f[i]$ as the minimum number of trips required to transport the first $i$ boxes from the warehouse to the corresponding docks, so the answer is $f[n]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# 33/39
class Solution:
    def boxDelivering(
        self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int
    ) -> int:
        n = len(boxes)
        ws = list(accumulate((box[1] for box in boxes), initial=0))
        c = [int(a != b) for a, b in pairwise(box[0] for box in boxes)]
        cs = list(accumulate(c, initial=0))
        f = [inf] * (n + 1)
        f[0] = 0
        for i in range(1, n + 1):
            for j in range(max(0, i - maxBoxes), i):
                if ws[i] - ws[j] <= maxWeight:
                    f[i] = min(f[i], f[j] + cs[i - 1] - cs[j] + 2)
        return f[n]

Continue Practicing

#1696 jump game vi #1425 constrained subsequence sum #2398 maximum number of robots within budget