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.
This approach involves iterating through the list of boxes and trying to load the ship with the maximum number of allowable boxes at each trip. Each trip should be calculated based on both box count and weight constraints. Once a maximum load is determined, calculate the necessary port visits and return trip to storage.
This solution iteratively calculates the maximum possible shipment for each trip and counts the necessary trips, including the return to storage. It makes use of a while loop to navigate through the boxes, taking into account box count and weight limitations. It also tracks different ports that need visits.
Python
JavaScript
Time Complexity: O(n), where n is the number of boxes. Space Complexity: O(portsCount), since we store the visited ports in a set.
In this approach, we use a dynamic programming array to keep track of the minimum number of trips required to deliver up to the i-th box. We update this array by considering the cost of adding boxes to the current trip while respecting weight and box constraints.
In this Java implementation, we utilize dynamic programming to compute the minimum number of trips needed. The dp array holds the minimum number of trips needed for up to i boxes. For each new box, we try to compute the cost adding it incurs and update our dp array based on previous computations.
Time Complexity: O(n), where n is the number of boxes. Space Complexity: O(n) due to the dp array.
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].
The boxes need to be transported in the order of the array. Each time, the truck will take out several consecutive boxes in order, then deliver them to the corresponding docks one by one. After all are delivered, it returns to the warehouse.
Therefore, we can enumerate the index j of the last box transported in the last trip. Then f[i] can be transferred from f[j]. During the transfer, we need to consider the following issues:
f[j], the number of boxes on the truck cannot exceed maxBoxesf[j], the total weight of the boxes on the truck cannot exceed maxWeightThe state transition equation is:
$
f[i] = min_{j \in [i - maxBoxes, i - 1]} \left(f[j] + sum_{k = j + 1}^i cost(k)\right)
Where sum_{k = j + 1}^i cost(k) represents the number of trips required to deliver the boxes in [j+1,..i] to their corresponding docks in one trip. This part of the trip count can be quickly calculated using prefix sums.
For example, suppose we take out boxes 1, 2, 3 and need to deliver them to docks 4, 4, 5. We first go from the warehouse to dock 4, then from dock 4 to dock 5, and finally from dock 5 back to the warehouse. It can be seen that it takes 2 trips to go from the warehouse to the dock and from the dock back to the warehouse. The number of trips from dock to dock depends on whether the two adjacent docks are the same. If they are not the same, the number of trips will increase by 1, otherwise it remains the same. Therefore, we can calculate the number of trips between docks using prefix sums, and add two trips for the start and end, to calculate the number of trips required to deliver the boxes in [j+1,..i] to their corresponding docks.
The code implementation is as follows:
# 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]
// 35/39
class Solution {
public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.length;
long[] ws = new long[n + 1];
int[] cs = new int[n];
for (int i = 0; i < n; ++i) {
int p = boxes[i][0], w = boxes[i][1];
ws[i + 1] = ws[i] + w;
if (i < n - 1) {
cs[i + 1] = cs[i] + (p != boxes[i + 1][0] ? 1 : 0);
}
}
int[] f = new int[n + 1];
Arrays.fill(f, 1 << 30);
f[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = Math.max(0, i - maxBoxes); j < i; ++j) {
if (ws[i] - ws[j] <= maxWeight) {
f[i] = Math.min(f[i], f[j] + cs[i - 1] - cs[j] + 2);
}
}
}
return f[n];
}
}
// 35/39
class Solution {
public:
int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.size();
long ws[n + 1];
int cs[n];
ws[0] = cs[0] = 0;
for (int i = 0; i < n; ++i) {
int p = boxes[i][0], w = boxes[i][1];
ws[i + 1] = ws[i] + w;
if (i < n - 1) cs[i + 1] = cs[i] + (p != boxes[i + 1][0]);
}
int f[n + 1];
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = max(0, i - maxBoxes); j < i; ++j) {
if (ws[i] - ws[j] <= maxWeight) {
f[i] = min(f[i], f[j] + cs[i - 1] - cs[j] + 2);
}
}
}
return f[n];
}
};
// 35/39
func boxDelivering(boxes [][]int, portsCount int, maxBoxes int, maxWeight int) int {
n := len(boxes)
ws := make([]int, n+1)
cs := make([]int, n)
for i, box := range boxes {
p, w := box[0], box[1]
ws[i+1] = ws[i] + w
if i < n-1 {
t := 0
if p != boxes[i+1][0] {
t++
}
cs[i+1] = cs[i] + t
}
}
f := make([]int, n+1)
for i := 1; i <= n; i++ {
f[i] = 1 << 30
for j := max(0, i-maxBoxes); j < i; j++ {
if ws[i]-ws[j] <= maxWeight {
f[i] = min(f[i], f[j]+cs[i-1]-cs[j]+2)
}
}
}
return f[n]
}
The data scale of this problem reaches 10^5, and the time complexity of the above code is O(n^2), which will exceed the time limit. If we observe carefully:
f[i] = min(f[i], f[j] + cs[i - 1] - cs[j] + 2)
In fact, we are looking for a j in the window [i-maxBoxes,..i-1] that minimizes the value of f[j] - cs[j]. To find the minimum value in a sliding window, a common method is to use a monotonic queue, which can get the minimum value that meets the condition in O(1) time.
The time complexity is O(n), and the space complexity is O(n). Here, n$ is the number of boxes in the problem.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the number of boxes. Space Complexity: O(portsCount), since we store the visited ports in a set. |
| Dynamic Programming Approach | Time Complexity: O(n), where n is the number of boxes. Space Complexity: O(n) due to the dp array. |
| Dynamic Programming + Monotonic Queue Optimization | — |
| 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. |
LeetCode 1687. Delivering Boxes from Storage to Ports • Happy Coding • 2,451 views views
Watch 5 more video solutions →Practice Delivering Boxes from Storage to Ports with our built-in code editor and test cases.
Practice on FleetCode