Delivering Boxes from Storage to Ports — Problem & Solution
Delivering Boxes from Storage to Ports solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Delivering Boxes from Storage to Ports is a hard coding problem on arrays, dynamic programming and prefix sum, asked in Amazon interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Prefix Sum, Queue, Monotonic Queue, Segment Tree
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A single delivery ship moves boxes from a storage yard to portsCount ports. boxes[i] = [port_i, weight_i] says box i must go to port port_i and weighs weight_i. The ship carries at most maxBoxes boxes and at most maxWeight total weight per load.
Boxes must be delivered in the given order. The ship repeats:
- At storage, load the next few waiting boxes (in order), within both limits.
- Sail to each loaded box's port in order and deliver it. If the next box goes to the port the ship is already at, no sailing is needed; every move to a different place is one trip.
- Sail back to storage — one more trip.
The ship must finish at storage. Return the minimum number of trips needed to deliver every box.
Example 1
Input: boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3
Output: 4
Explanation: One load of all three boxes: storage → 1 → 2 → 1 → storage is 4 trips.
Example 2
Input: boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6
Output: 6
Explanation: Load box 0 (2 trips), then boxes 1–3, which all go to port 3 (2 trips), then box 4 (2 trips).
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: Loads [0,1], [2,3] and [4,5] each visit a single port: 2 + 2 + 2 = 6 trips.
Constraints
1 <= boxes.length <= 10^51 <= portsCount, maxBoxes, maxWeight <= 10^51 <= port_i <= portsCount1 <= weight_i <= maxWeight
Hints for Delivering Boxes from Storage to Ports
Hint 1
A load of boxes
j..i-1always costs2plus the number of adjacent pairs inside it that go to different ports. Sodp[i] = min(dp[j] + 2 + changes(j, i-1))over loads that fit.Hint 2
Let
c[k]count port changes among the firstkboxes. Thenchanges(j, i-1) = c[i] - c[j+1], and the term to minimise isdp[j] - c[j+1], which does not depend oni.Hint 3
The valid
jform a sliding window (the box and weight limits only ever push its left end forward), so keep a monotonic deque ofjordered bydp[j] - c[j+1].
How to solve Delivering Boxes from Storage to Ports
Partition the box sequence into consecutive loads. A load's price is 2 plus its internal port changes, which splits into a part depending on its start and a part depending on its end — so the DP minimum over a sliding window of starts can be served by a monotonic deque.
Approach
- Build prefix weights
W[k]and change countsc[k](c[k]= number oftin[1, k-1]withport[t] != port[t-1]). dp[0] = 0. Fori = 1..n, the last load is boxesj..i-1withi - j <= maxBoxesandW[i] - W[j] <= maxWeight; its cost isdp[j] + c[i] - c[j+1] + 2.- Keep a deque of candidate
jwith increasingdp[j] - c[j+1]. Before computingdp[i], drop front entries that violate the box or weight limit; the front is the bestj. - After computing
dp[i](fori < n), pushi, first popping back entries whose key is not smaller. - Return
dp[n].
Why it works
The window of feasible starts only moves right as i grows, so an index that leaves it never returns, and an index dominated by a later one with no larger key can never be the minimum again. The front of the deque is therefore always the best feasible start, giving the same value as the quadratic DP.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- A load counts the return trip: a load to a single port is 2 trips, not 1.
- Port changes are counted only inside a load; the first box of a load is reached by the trip out of storage, already in the
+ 2. - The window is never empty: a single box always fits, since
weight_i <= maxWeightandmaxBoxes >= 1.
Reference solution
Python
from typing import List
from collections import deque
def boxDelivering(boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:
n = len(boxes)
W = [0] * (n + 1)
c = [0] * (n + 1)
for k in range(1, n + 1):
W[k] = W[k - 1] + boxes[k - 1][1]
if k >= 2:
c[k] = c[k - 1] + (1 if boxes[k - 1][0] != boxes[k - 2][0] else 0)
dp = [0] * (n + 1)
dq = deque([0])
for i in range(1, n + 1):
while i - dq[0] > maxBoxes or W[i] - W[dq[0]] > maxWeight:
dq.popleft()
j = dq[0]
dp[i] = dp[j] - c[j + 1] + c[i] + 2
if i < n:
key = dp[i] - c[i + 1]
while dq and dp[dq[-1]] - c[dq[-1] + 1] >= key:
dq.pop()
dq.append(i)
return dp[n]Java
public static int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.length;
long[] W = new long[n + 1];
int[] c = new int[n + 1];
for (int k = 1; k <= n; k++) {
W[k] = W[k - 1] + boxes[k - 1][1];
if (k >= 2) c[k] = c[k - 1] + (boxes[k - 1][0] != boxes[k - 2][0] ? 1 : 0);
}
int[] dp = new int[n + 1];
int[] dq = new int[n + 1];
int head = 0, tail = 0;
dq[tail++] = 0;
for (int i = 1; i <= n; i++) {
while (i - dq[head] > maxBoxes || W[i] - W[dq[head]] > maxWeight) head++;
int j = dq[head];
dp[i] = dp[j] - c[j + 1] + c[i] + 2;
if (i < n) {
int key = dp[i] - c[i + 1];
while (tail > head && dp[dq[tail - 1]] - c[dq[tail - 1] + 1] >= key) tail--;
dq[tail++] = i;
}
}
return dp[n];
}C++
int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.size();
vector<long long> W(n + 1, 0);
vector<int> c(n + 1, 0);
for (int k = 1; k <= n; k++) {
W[k] = W[k - 1] + boxes[k - 1][1];
if (k >= 2) c[k] = c[k - 1] + (boxes[k - 1][0] != boxes[k - 2][0] ? 1 : 0);
}
vector<int> dp(n + 1, 0);
deque<int> dq;
dq.push_back(0);
for (int i = 1; i <= n; i++) {
while (i - dq.front() > maxBoxes || W[i] - W[dq.front()] > maxWeight) dq.pop_front();
int j = dq.front();
dp[i] = dp[j] - c[j + 1] + c[i] + 2;
if (i < n) {
int key = dp[i] - c[i + 1];
while (!dq.empty() && dp[dq.back()] - c[dq.back() + 1] >= key) dq.pop_back();
dq.push_back(i);
}
}
return dp[n];
}JavaScript
var boxDelivering = function(boxes, portsCount, maxBoxes, maxWeight) {
var n = boxes.length, W = new Array(n + 1).fill(0), c = new Array(n + 1).fill(0);
for (var k = 1; k <= n; k++) {
W[k] = W[k - 1] + boxes[k - 1][1];
if (k >= 2) c[k] = c[k - 1] + (boxes[k - 1][0] !== boxes[k - 2][0] ? 1 : 0);
}
var dp = new Array(n + 1).fill(0), dq = new Array(n + 1), head = 0, tail = 0;
dq[tail++] = 0;
for (var i = 1; i <= n; i++) {
while (i - dq[head] > maxBoxes || W[i] - W[dq[head]] > maxWeight) head++;
var j = dq[head];
dp[i] = dp[j] - c[j + 1] + c[i] + 2;
if (i < n) {
var key = dp[i] - c[i + 1];
while (tail > head && dp[dq[tail - 1]] - c[dq[tail - 1] + 1] >= key) tail--;
dq[tail++] = i;
}
}
return dp[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming