# Delivering Boxes from Storage to Ports **Difficulty:** HARD [External](https://leetcode.com/problems/delivering-boxes-from-storage-to-ports) Canonical: https://scaleengineer.com/dsa/problems/delivering-boxes-from-storage-to-ports **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum) **Data structures:** Array, Heap (Priority Queue), Segment Tree, Queue, Monotonic Queue **Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix) --- ## Problem 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] = [ports​​i​, weighti]`, and three integers `portsCount`, `maxBoxes`, and `maxWeight`. * `ports​​i` 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: * The ship will take some number of boxes from the `boxes` queue, not violating the `maxBoxes` and `maxWeight` constraints. * For each loaded box **in order**, the ship will make a **trip** to the port the box needs to be delivered to and deliver it. If the ship is already at the correct port, no **trip** is needed, and the box can immediately be delivered. * The ship then makes a return **trip** to storage to take more boxes from the queue. 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 <= 105` * `1 <= portsCount, maxBoxes, maxWeight <= 105` * `1 <= ports​​i <= portsCount` * `1 <= weightsi <= maxWeight` # Approaches ## Dynamic Programming This approach uses dynamic programming to find the minimum number of trips. We define `dp[i]` as the minimum trips required to deliver the first `i` boxes. To compute `dp[i]`, we consider every possible last voyage, which could start at any box `j` (where `0 <= j < i`) and end at box `i-1`. We then choose the starting box `j` that minimizes the total trips, which is the sum of trips for the first `j` boxes (`dp[j]`) and the trips for the last voyage (`cost(j, i-1)`). **Time:** O(N^2), where N is the number of boxes. The two nested loops for `i` and `j` dominate the runtime. · **Space:** O(N), where N is the number of boxes. This is for storing the `dp` array and the prefix sum arrays. **Pros:** It's a straightforward and correct implementation of the DP recurrence.; It's easier to understand and implement compared to more optimized solutions. **Cons:** The `O(N^2)` time complexity is too slow for the given constraints (`N <= 10^5`), and will likely result in a 'Time Limit Exceeded' error. ### Explanation The core of this method is the recurrence relation `dp[i] = min(dp[j] + cost(j, i-1))`, where `dp[i]` is the minimum cost for the first `i` boxes, and `cost(j, i-1)` is the cost of a single voyage delivering boxes from `j` to `i-1`. A voyage is only possible if the number of boxes (`i-j`) and their total weight do not exceed `maxBoxes` and `maxWeight` respectively. The cost of a voyage `j..i-1` is `2 + (number of port changes)`. The two trips account for the initial travel from storage to the port of box `j` and the final return trip from the port of box `i-1` to storage. The number of port changes is the count of adjacent boxes in the sequence `j..i-1` that are delivered to different ports. To implement this efficiently and avoid an `O(N^3)` solution, we precompute prefix sums for weights and port changes. This allows us to calculate the total weight and number of changes for any sub-array of boxes in `O(1)` time. The DP calculation then involves a nested loop structure, leading to an overall time complexity of `O(N^2)`. ```java class Solution { public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) { int n = boxes.length; long[] prefixWeight = new long[n + 1]; for (int i = 0; i < n; i++) { prefixWeight[i + 1] = prefixWeight[i] + boxes[i][1]; } // prefixChanges[i] = number of port changes in boxes[0...i] int[] prefixChanges = new int[n]; for (int i = 1; i < n; i++) { prefixChanges[i] = prefixChanges[i - 1] + (boxes[i][0] != boxes[i - 1][0] ? 1 : 0); } int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE / 2); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = i - 1; j >= 0; j--) { long currentWeight = prefixWeight[i] - prefixWeight[j]; int currentBoxes = i - j; if (currentBoxes > maxBoxes || currentWeight > maxWeight) { break; } // Cost for voyage with boxes j..i-1 // Number of port changes is sum_{k=j to i-2} (port_{k+1} != port_k) // This is equivalent to prefixChanges[i-1] - prefixChanges[j] int portChanges = (i > 1 ? prefixChanges[i - 1] : 0) - (j > 0 ? prefixChanges[j] : 0); int cost = 2 + portChanges; dp[i] = Math.min(dp[i], dp[j] + cost); } } return dp[n]; } } ``` ### Algorithm 1. Let `n` be the number of boxes. 2. Define `dp[i]` as the minimum number of trips to deliver the first `i` boxes (from index `0` to `i-1`). Our goal is to find `dp[n]`. 3. The base case is `dp[0] = 0` (zero trips for zero boxes). 4. To compute `dp[i]`, we iterate through all possible start points `j` (`0 <= j < i`) for the last voyage. This last voyage will deliver boxes from `j` to `i-1`. 5. The recurrence relation is `dp[i] = min(dp[j] + cost(j, i-1))` over all valid `j`. 6. A starting point `j` is valid if the voyage for boxes `j..i-1` does not exceed `maxBoxes` and `maxWeight`. 7. The cost for a voyage with boxes `j..i-1` is `2 + (number of port changes)`. The `2` trips are for going from storage to the first port (`port_j`) and returning to storage from the last port (`port_{i-1}`). 8. To avoid recomputing weights and port changes repeatedly, we precompute prefix sums: - `prefixWeight[i]` stores the total weight of boxes `0..i-1`. - `prefixChanges[i]` stores the number of port changes within boxes `0..i` (i.e., between `box_k` and `box_{k+1}` for `k` from `0` to `i-1`). 9. With precomputation, the total weight for voyage `j..i-1` is `prefixWeight[i] - prefixWeight[j]`. The number of port changes is `prefixChanges[i-1] - prefixChanges[j]`. 10. The main algorithm consists of two nested loops: an outer loop for `i` from `1` to `n`, and an inner loop for `j` from `i-1` down to `0`. 11. Inside the inner loop, we check the constraints. If valid, we calculate the cost and update `dp[i]`. If invalid, we can break the inner loop since further decreasing `j` will only increase the box count and weight. ## Optimized DP with Sliding Window Deque This approach optimizes the `O(N^2)` DP solution by recognizing that the calculation for `dp[i]` involves finding a minimum value over a sliding window. By rewriting the recurrence relation, we can isolate the terms dependent on the inner loop variable `j`. This structure is a classic pattern solvable with a monotonic deque. The deque efficiently tracks the best previous state `j` in amortized `O(1)` time, which reduces the overall time complexity to linear. **Time:** O(N), where N is the number of boxes. The main loop runs `N` times, and each index is pushed onto and popped from the deque at most once, making the deque operations amortized `O(1)`. · **Space:** O(N), where N is the number of boxes. This is for the `dp` array, prefix sum arrays, and the deque, which can store up to `N` elements in the worst case. **Pros:** Highly efficient with `O(N)` time complexity, which passes the given constraints.; Demonstrates a powerful optimization technique for a class of DP problems. **Cons:** The logic is more complex and harder to implement correctly compared to the straightforward `O(N^2)` DP.; Requires careful handling of array indices and deque operations. ### Explanation We start with the same recurrence relation as the `O(N^2)` approach. By rearranging it to `dp[i] = (2 + prefixChanges[i-1]) + min_{j} (dp[j] - prefixChanges[j])`, we see that for a fixed `i`, the first part is constant. The task is to find the minimum of `dp[j] - prefixChanges[j]` over all valid previous states `j`. The set of valid `j`'s forms a 'sliding window' that moves as `i` increases. The window is constrained by `maxBoxes` and `maxWeight`. This is a perfect scenario for the sliding window minimum algorithm using a monotonic deque. The deque stores indices `j` from previous states. It is kept monotonic with respect to the value `g(j) = dp[j] - prefixChanges[j]`. For each `i`, we first prune the deque by removing indices from the front that are no longer valid. The index at the front of the deque then gives us the optimal `j` to calculate `dp[i]`. Finally, we add the current index `i` to the deque while maintaining its monotonic property. This process ensures that each index is added to and removed from the deque at most once, leading to an `O(N)` time complexity. ```java class Solution { public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) { int n = boxes.length; long[] prefixWeight = new long[n + 1]; for (int i = 0; i < n; i++) { prefixWeight[i + 1] = prefixWeight[i] + boxes[i][1]; } int[] prefixChanges = new int[n]; for (int i = 1; i < n; i++) { prefixChanges[i] = prefixChanges[i - 1] + (boxes[i][0] != boxes[i - 1][0] ? 1 : 0); } long[] dp = new long[n + 1]; long[] g = new long[n + 1]; // g[j] = dp[j] - prefixChanges[j] Deque dq = new ArrayDeque<>(); dq.offerLast(0); g[0] = 0; // dp[0] = 0, and let's consider prefixChanges[-1] as 0, so g[0] = dp[0] - 0 = 0 for (int i = 1; i <= n; i++) { // Prune deque based on window constraints while (!dq.isEmpty() && (i - dq.peekFirst() > maxBoxes || prefixWeight[i] - prefixWeight[dq.peekFirst()] > maxWeight)) { dq.pollFirst(); } int bestJ = dq.peekFirst(); // dp[i] = (2 + prefixChanges[i-1]) + g[bestJ] // g[bestJ] = dp[bestJ] - prefixChanges[bestJ-1] (if we define it that way) // Let's use the direct formula: dp[i] = dp[bestJ] + cost(bestJ, i-1) dp[i] = dp[bestJ] + 2 + (prefixChanges[i - 1] - (bestJ > 0 ? prefixChanges[bestJ - 1] : 0)); // This is getting complex. Let's use the g(j) formulation which is cleaner. // dp[i] = g[bestJ] + 2 + prefixChanges[i-1] // Let's redefine g(j) = dp[j] + (2 - prefixChanges[j-1]) // Let's stick to the math: dp[i] = (2 + prefixChanges[i-1]) + min(dp[j] - prefixChanges[j]) // Let's use prefixChanges of size n+1 for simpler indexing int[] pChanges = new int[n + 1]; for(int k=0; k maxBoxes || prefixWeight[k] - prefixWeight[dq.peekFirst()] > maxWeight)) { dq.pollFirst(); } dp[k] = costToOptimize[dq.peekFirst()] + 2 + pChanges[k]; costToOptimize[k] = dp[k] - pChanges[k+1 > n ? k : k+1]; while(!dq.isEmpty() && costToOptimize[dq.peekLast()] >= costToOptimize[k]) { dq.pollLast(); } dq.offerLast(k); } return (int)dp[n]; } } ``` ### Algorithm 1. The DP recurrence is `dp[i] = min_{j} (dp[j] + 2 + prefixChanges[i-1] - prefixChanges[j])`. 2. Rearrange the formula: `dp[i] = (2 + prefixChanges[i-1]) + min_{j} (dp[j] - prefixChanges[j])`. 3. Let `g(j) = dp[j] - prefixChanges[j]`. The problem reduces to finding `min(g(j))` over a sliding window of valid `j`'s for each `i`. 4. The constraints on `j` define the window: - `i - j <= maxBoxes` - `prefixWeight[i] - prefixWeight[j] <= maxWeight` 5. Use a monotonic deque (double-ended queue) to maintain indices `j` such that their corresponding `g(j)` values are monotonically increasing. This allows finding `min(g(j))` in amortized `O(1)` time. 6. Initialize `dp` and `g` arrays, and a deque with index `0`. 7. Loop `i` from `1` to `n`: a. Remove indices `j` from the front of the deque that are outside the valid window (violating `maxBoxes` or `maxWeight` constraints). b. The optimal `j` (`best_j`) is now at the front of the deque. Calculate `dp[i]` using `g(best_j)`: `dp[i] = g[best_j] + 2 + prefixChanges[i-1]`. c. Calculate `g(i) = dp[i] - prefixChanges[i]`. d. To maintain the deque's monotonic property, remove all indices `k` from the back of the deque where `g(k) >= g(i)`. e. Add `i` to the back of the deque. 8. Return `dp[n]`. # Solutions ### Java ```java class Solution { public int boxDelivering ( int [][] boxes , int portsCount , int maxBoxes , int maxWeight ) { int length = boxes . length ; int [] ports = new int [ length + 1 ]; int [] weights = new int [ length + 1 ]; int [] differences = new int [ length + 1 ]; long [] prefixWeights = new long [ length + 1 ]; for ( int i = 1 ; i <= length ; i ++) { ports [ i ] = boxes [ i - 1 ][ 0 ]; weights [ i ] = boxes [ i - 1 ][ 1 ]; if ( i > 1 ) differences [ i ] = differences [ i - 1 ] + ( ports [ i - 1 ] != ports [ i ] ? 1 : 0 ); prefixWeights [ i ] = prefixWeights [ i - 1 ] + weights [ i ]; } Deque < Integer > deque = new LinkedList < Integer >(); deque . offerLast ( 0 ); int [] dp = new int [ length + 1 ]; int [] remain = new int [ length + 1 ]; for ( int i = 1 ; i <= length ; i ++) { while (! deque . isEmpty () && ( i - deque . peekFirst () > maxBoxes || prefixWeights [ i ] - prefixWeights [ deque . peekFirst ()] > maxWeight )) deque . pollFirst (); dp [ i ] = remain [ deque . peekFirst ()] + differences [ i ] + 2 ; if ( i != length ) { remain [ i ] = dp [ i ] - differences [ i + 1 ]; while (! deque . isEmpty () && remain [ i ] <= remain [ deque . peekLast ()]) deque . pollLast (); deque . offerLast ( i ); } } return dp [ length ]; } } ############ 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 ]; Deque < Integer > q = new ArrayDeque <>(); q . offer ( 0 ); for ( int i = 1 ; i <= n ; ++ i ) { while (! q . isEmpty () && ( i - q . peekFirst () > maxBoxes || ws [ i ] - ws [ q . peekFirst ()] > maxWeight )) { q . pollFirst (); } if (! q . isEmpty ()) { f [ i ] = cs [ i - 1 ] + f [ q . peekFirst ()] - cs [ q . peekFirst ()] + 2 ; } if ( i < n ) { while (! q . isEmpty () && f [ q . peekLast ()] - cs [ q . peekLast ()] >= f [ i ] - cs [ i ]) { q . pollLast (); } q . offer ( i ); } } return f [ n ]; } } ``` ### Python ```python 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 = [0] * (n + 1) q = deque([0]) for i in range(1, n + 1): while q and (i - q[0] > maxBoxes or ws[i] - ws[q[0]] > maxWeight): q . popleft() if q: f[i] = cs[i - 1] + f[q[0]] - cs[q[0]] + 2 if i < n: while q and f[q[- 1]] - cs[q[- 1]] >= f[i] - cs[i]: q . pop() q . append(i) return f[n] ``` ### CPP ```cpp class Solution { public: int boxDelivering(vector> &boxes, int portsCount, int maxBoxes, int maxWeight) { int n = boxes.size(); long ws[n + 1]; int f[n + 1]; int cs[n]; ws[0] = cs[0] = f[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]); } deque q{{0}}; for (int i = 1; i <= n; ++i) { while (!q.empty() && (i - q.front() > maxBoxes || ws[i] - ws[q.front()] > maxWeight)) q.pop_front(); if (!q.empty()) f[i] = cs[i - 1] + f[q.front()] - cs[q.front()] + 2; if (i < n) { while (!q.empty() && f[q.back()] - cs[q.back()] >= f[i] - cs[i]) q.pop_back(); q.push_back(i); } } return f[n]; } }; ```