LeetCode 1687 - Delivering Boxes from Storage to Ports
This problem asks us to minimize the total number of ship trips required to deliver boxes from storage to ports, while r
Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Segment Tree, Queue, Heap (Priority Queue), Prefix Sum, Monotonic Queue
Solution
Problem Understanding
This problem asks us to minimize the total number of ship trips required to deliver boxes from storage to ports, while respecting two constraints:
- The ship can carry at most
maxBoxesboxes at once. - The total weight of the loaded boxes cannot exceed
maxWeight.
The boxes must be delivered in the exact order they appear in the input array. This ordering restriction is extremely important because it prevents us from freely regrouping boxes by port.
Each box is represented as:
boxes[i] = [port_i, weight_i]
where:
port_iis the destination portweight_iis the box weight
The ship starts at storage. For every batch of boxes loaded:
- It visits ports in the order required by the boxes.
- Moving from one port to another counts as one trip.
- Returning from the final port back to storage also counts as one trip.
If consecutive boxes go to the same port, the ship does not need an additional trip between them because it is already at that port.
The goal is to compute the minimum total number of trips needed to deliver all boxes and return to storage at the end.
The constraints are very large:
1 <= boxes.length <= 100000
This immediately tells us that quadratic solutions are too slow. Any algorithm close to O(n^2) will time out. We need an approach around O(n) or O(n log n).
Several aspects make this problem tricky:
- Boxes must remain in order.
- A shipment may contain multiple ports.
- Consecutive equal ports reduce travel cost.
- Weight and box-count constraints both affect valid shipment boundaries.
- A locally optimal shipment is not always globally optimal.
An important observation is that the cost of one shipment depends on the number of port transitions inside that shipment.
For example:
[1,1], [1,2], [2,1], [2,3], [3,1]
The ship path becomes:
storage -> 1 -> 2 -> 3 -> storage
The number of trips is:
(number of port changes) + 2
The +2 comes from:
- leaving storage
- returning to storage
Edge cases that can easily cause bugs include:
- All boxes going to the same port
- Every box going to a different port
- Weight limit forcing tiny shipments
maxBoxes = 1- A shipment boundary occurring exactly at the weight limit
- Consecutive equal ports at the edge of a shipment
The problem guarantees that every individual box weight is at most maxWeight, so every box can always be shipped eventually.
Approaches
Brute Force Approach
A brute-force dynamic programming solution would try every possible previous split point.
Define:
dp[i] = minimum trips needed to deliver first i boxes
For each i, we try all valid j < i such that boxes [j, i-1] can fit into one shipment.
The transition becomes:
dp[i] = min(dp[j] + cost(j, i-1))
where:
cost(j, i-1)is the number of port transitions inside the shipment plus the return trip.
To compute this, we must:
- Check whether the segment satisfies:
- box count constraint
- weight constraint
- Count port changes inside the segment.
This solution is correct because it explores every possible valid partition of shipments.
However, it is too slow.
There are O(n^2) possible intervals, and even with prefix sums the DP still becomes quadratic.
With n = 100000, this is infeasible.
Key Insight Behind the Optimal Solution
The critical observation is that shipment validity forms a sliding window.
For each ending position i, there exists a left boundary j such that:
[j, i]
is the largest valid shipment.
As i increases, j only moves forward.
This monotonic behavior allows us to use:
- prefix sums
- sliding window
- monotonic queue optimization
We transform the DP transition into a form where we maintain the best candidate dynamically.
The optimized recurrence becomes:
dp[i] = min(dp[j] + transitionCost)
where the transition cost can be rewritten using prefix information.
This allows each index to enter and leave the deque once, producing an O(n) solution.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2) |
O(n) |
Tries every valid shipment interval |
| Optimal | O(n) |
O(n) |
Uses DP, prefix sums, sliding window, and monotonic queue |
Algorithm Walkthrough
Prefix Definitions
We first preprocess several arrays.
Let:
weights[i] = weight of box i
ports[i] = destination port of box i
We build:
prefixWeight[i]
which stores total weight of first i boxes.
We also build:
portChanges[i]
where:
portChanges[i]
equals the number of port transitions among first i boxes.
For example:
ports = [1,1,2,2,3]
then:
portChanges = [0,0,1,1,2]
DP State
Define:
dp[i]
as the minimum trips needed to deliver first i boxes.
The answer is:
dp[n]
Shipment Cost Formula
Suppose we deliver boxes from index j to i-1.
The trip cost equals:
(number of port changes inside segment) + 2
The +2 comes from:
- leaving storage
- returning to storage
Using prefix arrays:
cost(j, i-1)
=
(portChanges[i-1] - portChanges[j]) + 2
Therefore:
dp[i]
=
min(
dp[j]
+ portChanges[i-1]
- portChanges[j]
+ 2
)
Rearrange:
dp[i]
=
portChanges[i-1] + 2
+
min(dp[j] - portChanges[j])
Now the optimization target becomes:
dp[j] - portChanges[j]
Sliding Window Constraints
For every i, we must ensure shipment [j, i-1] satisfies:
- Number of boxes:
i - j <= maxBoxes
- Total weight:
prefixWeight[i] - prefixWeight[j] <= maxWeight
As i increases, invalid j values are removed from the front.
Monotonic Queue
We maintain a deque of candidate indices j.
The deque is ordered by increasing value of:
dp[j] - portChanges[j]
For each i:
- Remove invalid indices from the front.
- Front of deque gives optimal
j. - Compute
dp[i]. - Insert
iinto deque while maintaining monotonic order.
Each index is inserted and removed once, giving linear complexity.
Why it works
The DP guarantees optimality because every valid shipment ending at position i is considered.
The sliding window ensures only feasible shipments remain.
The monotonic queue works because the DP transition depends only on the minimum value of:
dp[j] - portChanges[j]
among valid candidates. Since invalid candidates leave permanently and new candidates enter once, maintaining the minimum in a deque produces the correct optimal transition efficiently.
Python Solution
from collections import deque
from typing import List
class Solution:
def boxDelivering(
self,
boxes: List[List[int]],
portsCount: int,
maxBoxes: int,
maxWeight: int
) -> int:
n = len(boxes)
ports = [0] * n
weights = [0] * n
for i in range(n):
ports[i] = boxes[i][0]
weights[i] = boxes[i][1]
prefix_weight = [0] * (n + 1)
for i in range(n):
prefix_weight[i + 1] = prefix_weight[i] + weights[i]
port_changes = [0] * n
for i in range(1, n):
port_changes[i] = port_changes[i - 1]
if ports[i] != ports[i - 1]:
port_changes[i] += 1
dp = [0] * (n + 1)
dq = deque([0])
for i in range(1, n + 1):
while dq and (
i - dq[0] > maxBoxes or
prefix_weight[i] - prefix_weight[dq[0]] > maxWeight
):
dq.popleft()
j = dq[0]
dp[i] = (
dp[j]
+ port_changes[i - 1]
- (port_changes[j] if j < n else 0)
+ 2
)
if i < n:
current_value = dp[i] - port_changes[i]
while dq:
back = dq[-1]
back_value = dp[back] - (
port_changes[back] if back < n else 0
)
if back_value <= current_value:
break
dq.pop()
dq.append(i)
return dp[n]
The implementation begins by separating ports and weights into individual arrays for cleaner indexing.
Next, prefix sums are constructed for weights so we can check shipment weight constraints in constant time.
The port_changes array tracks how many times the destination port changes while traversing the boxes. This allows us to compute shipment travel cost in constant time.
The DP array stores the minimum trips required for the first i boxes.
The deque maintains candidate shipment starting points. Before processing each i, invalid candidates are removed if they violate either:
- maximum number of boxes
- maximum weight
The front of the deque always contains the best valid transition because the deque is maintained in increasing order of:
dp[j] - port_changes[j]
After computing dp[i], the current index is inserted while preserving monotonicity.
Because every index enters and leaves the deque once, the algorithm runs in linear time.
Go Solution
package main
func boxDelivering(boxes [][]int, portsCount int, maxBoxes int, maxWeight int) int {
n := len(boxes)
ports := make([]int, n)
weights := make([]int, n)
for i := 0; i < n; i++ {
ports[i] = boxes[i][0]
weights[i] = boxes[i][1]
}
prefixWeight := make([]int, n+1)
for i := 0; i < n; i++ {
prefixWeight[i+1] = prefixWeight[i] + weights[i]
}
portChanges := make([]int, n)
for i := 1; i < n; i++ {
portChanges[i] = portChanges[i-1]
if ports[i] != ports[i-1] {
portChanges[i]++
}
}
dp := make([]int, n+1)
deque := make([]int, 0)
deque = append(deque, 0)
for i := 1; i <= n; i++ {
for len(deque) > 0 &&
(i-deque[0] > maxBoxes ||
prefixWeight[i]-prefixWeight[deque[0]] > maxWeight) {
deque = deque[1:]
}
j := deque[0]
changeJ := 0
if j < n {
changeJ = portChanges[j]
}
dp[i] = dp[j] + portChanges[i-1] - changeJ + 2
if i < n {
currentValue := dp[i] - portChanges[i]
for len(deque) > 0 {
back := deque[len(deque)-1]
backValue := dp[back]
if back < n {
backValue -= portChanges[back]
}
if backValue <= currentValue {
break
}
deque = deque[:len(deque)-1]
}
deque = append(deque, i)
}
}
return dp[n]
}
The Go implementation follows the same logic as the Python version but uses slices to implement the deque.
Go does not provide a built-in deque structure, so we simulate one using slice operations:
deque[1:]removes the frontdeque[:len(deque)-1]removes the back
All values fit safely inside Go int because the maximum number of trips is bounded by a small multiple of n.
Worked Examples
Example 1
boxes = [[1,1],[2,1],[1,1]]
maxBoxes = 3
maxWeight = 3
Preprocessing
Ports:
[1,2,1]
Weights:
[1,1,1]
Prefix weights:
[0,1,2,3]
Port changes:
[0,1,2]
DP Iteration
| i | Valid j values | Best j | dp[i] |
|---|---|---|---|
| 1 | [0] | 0 | 2 |
| 2 | [0] | 0 | 3 |
| 3 | [0] | 0 | 4 |
Final answer:
4
Ship route:
storage -> 1 -> 2 -> 1 -> storage
Example 2
boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]]
Prefix Arrays
Ports:
[1,3,3,3,2]
Port changes:
[0,1,1,1,2]
Prefix weights:
[0,2,5,6,7,11]
DP States
| i | Best Shipment | dp[i] |
|---|---|---|
| 1 | [1] | 2 |
| 2 | [1,2] | 3 |
| 3 | [2,3] | 4 |
| 4 | [2,3,4] | 4 |
| 5 | [5] | 6 |
Final answer:
6
Example 3
boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]]
Prefix Weights
[0,4,6,7,8,10,14]
Port Changes
[0,0,1,1,2,2]
Optimal Partition
| Shipment | Cost |
|---|---|
| boxes 1-2 | 2 |
| boxes 3-4 | 2 |
| boxes 5-6 | 2 |
Total:
6
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) |
Every index enters and leaves deque once |
| Space | O(n) |
Prefix arrays, DP array, and deque |
The algorithm is linear because all sliding window operations are amortized constant time. The monotonic queue never processes an index more than twice, once when inserted and once when removed.
Test Cases
sol = Solution()
# Example 1
assert sol.boxDelivering(
[[1,1],[2,1],[1,1]],
2,
3,
3
) == 4 # alternating ports in one shipment
# Example 2
assert sol.boxDelivering(
[[1,2],[3,3],[3,1],[3,1],[2,4]],
3,
3,
6
) == 6 # optimal grouping by port
# Example 3
assert sol.boxDelivering(
[[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]],
3,
6,
7
) == 6 # weight constraints split shipments
# Single box
assert sol.boxDelivering(
[[1,5]],
1,
1,
5
) == 2 # storage -> port -> storage
# All boxes same port
assert sol.boxDelivering(
[[1,1],[1,1],[1,1]],
1,
3,
3
) == 2 # only one port visit needed
# maxBoxes forces separate trips
assert sol.boxDelivering(
[[1,1],[2,1],[3,1]],
3,
1,
10
) == 6 # every box separate
# Weight constraint forces splits
assert sol.boxDelivering(
[[1,5],[2,5],[3,5]],
3,
3,
5
) == 6 # each box alone due to weight
# Consecutive identical ports
assert sol.boxDelivering(
[[1,1],[1,1],[2,1],[2,1]],
2,
4,
4
) == 3 # storage -> 1 -> 2 -> storage
# Large valid single shipment
assert sol.boxDelivering(
[[1,1],[2,1],[2,1],[3,1]],
3,
10,
10
) == 4 # one shipment across multiple ports
# Exact weight boundary
assert sol.boxDelivering(
[[1,2],[2,3]],
2,
2,
5
) == 3 # shipment exactly at weight limit
Test Summary
| Test | Why |
|---|---|
| Example 1 | Basic alternating-port scenario |
| Example 2 | Demonstrates grouping optimization |
| Example 3 | Weight constraints split shipments |
| Single box | Smallest valid input |
| All boxes same port | Ensures port transitions handled correctly |
| maxBoxes = 1 | Forces every box into separate shipment |
| Weight-limited shipments | Validates sliding weight window |
| Consecutive equal ports | Ensures no unnecessary trips counted |
| Single large shipment | Tests maximum grouping |
| Exact weight boundary | Verifies inclusive constraint handling |
Edge Cases
All Boxes Go To The Same Port
If every box has the same destination port, the optimal strategy is usually to load as many as possible into one shipment. A buggy implementation may incorrectly count multiple port visits.
For example:
[[1,1],[1,1],[1,1]]
should require only:
storage -> 1 -> storage
which equals 2 trips.
The implementation handles this correctly because port_changes does not increase for consecutive identical ports.
Weight Constraint Forces Tiny Shipments
A common mistake is assuming box-count limits are the only constraint.
For example:
maxBoxes = 10
maxWeight = 5
with:
[[1,5],[2,5],[3,5]]
Each shipment can carry only one box despite the generous box limit.
The sliding window explicitly checks both:
i - j <= maxBoxes
and
prefixWeight[i] - prefixWeight[j] <= maxWeight
so overweight windows are removed immediately.
Shipment Boundary Around Port Changes
Off-by-one errors frequently occur when computing port transitions.
Consider:
[1,1,2,2,3]
The number of transitions is:
1 -> 2
2 -> 3
which equals 2, not 4.
The implementation avoids double-counting by storing cumulative transition counts in port_changes and using prefix subtraction to compute transitions inside any shipment interval correctly.