Delivering Boxes from Storage to Ports

Hard

#1547Time: 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.1 company

Patterns

Dynamic Programming Prefix Sum

Data structures

Array Heap (Priority Queue)Segment Tree Queue Monotonic Queue

Companies

Nutanix

Prompt

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, weight_i], and three integers portsCount, maxBoxes, and maxWeight.

ports_i is the port where you need to deliver the i^th box and weights_i is the weight of the i^th 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 <= 10⁵
1 <= portsCount, maxBoxes, maxWeight <= 10⁵
1 <= ports_i <= portsCount
1 <= weights_i <= maxWeight

Approaches

2 approaches with complexity analysis and trade-offs.

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)).

Algorithm

Let n be the number of boxes.
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].
The base case is dp[0] = 0 (zero trips for zero boxes).
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.
The recurrence relation is dp[i] = min(dp[j] + cost(j, i-1)) over all valid j.
A starting point j is valid if the voyage for boxes j..i-1 does not exceed maxBoxes and maxWeight.
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}).
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).
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].
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.
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.

Walkthrough

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).

1class Solution {2    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {3        int n = boxes.length;4        long[] prefixWeight = new long[n + 1];5        for (int i = 0; i < n; i++) {6            prefixWeight[i + 1] = prefixWeight[i] + boxes[i][1];7        }8 9        // prefixChanges[i] = number of port changes in boxes[0...i]10        int[] prefixChanges = new int[n];11        for (int i = 1; i < n; i++) {12            prefixChanges[i] = prefixChanges[i - 1] + (boxes[i][0] != boxes[i - 1][0] ? 1 : 0);13        }14 15        int[] dp = new int[n + 1];16        Arrays.fill(dp, Integer.MAX_VALUE / 2);17        dp[0] = 0;18 19        for (int i = 1; i <= n; i++) {20            for (int j = i - 1; j >= 0; j--) {21                long currentWeight = prefixWeight[i] - prefixWeight[j];22                int currentBoxes = i - j;23 24                if (currentBoxes > maxBoxes || currentWeight > maxWeight) {25                    break;26                }27 28                // Cost for voyage with boxes j..i-129                // Number of port changes is sum_{k=j to i-2} (port_{k+1} != port_k)30                // This is equivalent to prefixChanges[i-1] - prefixChanges[j]31                int portChanges = (i > 1 ? prefixChanges[i - 1] : 0) - (j > 0 ? prefixChanges[j] : 0);32                int cost = 2 + portChanges;33 34                dp[i] = Math.min(dp[i], dp[j] + cost);35            }36        }37        return dp[n];38    }39}

Complexity

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.

Trade-offs

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.

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.

Algorithm

The DP recurrence is dp[i] = min_{j} (dp[j] + 2 + prefixChanges[i-1] - prefixChanges[j]).
Rearrange the formula: dp[i] = (2 + prefixChanges[i-1]) + min_{j} (dp[j] - prefixChanges[j]).
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.
The constraints on j define the window:
- i - j <= maxBoxes
- prefixWeight[i] - prefixWeight[j] <= maxWeight
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.
Initialize dp and g arrays, and a deque with index 0.
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.
Return dp[n].

Walkthrough

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.

1class Solution {2    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {3        int n = boxes.length;4        long[] prefixWeight = new long[n + 1];5        for (int i = 0; i < n; i++) {6            prefixWeight[i + 1] = prefixWeight[i] + boxes[i][1];7        }8 9        int[] prefixChanges = new int[n];10        for (int i = 1; i < n; i++) {11            prefixChanges[i] = prefixChanges[i - 1] + (boxes[i][0] != boxes[i - 1][0] ? 1 : 0);12        }13 14        long[] dp = new long[n + 1];15        long[] g = new long[n + 1]; // g[j] = dp[j] - prefixChanges[j]16 17        Deque<Integer> dq = new ArrayDeque<>();18        dq.offerLast(0);19        g[0] = 0; // dp[0] = 0, and let's consider prefixChanges[-1] as 0, so g[0] = dp[0] - 0 = 020 21        for (int i = 1; i <= n; i++) {22            // Prune deque based on window constraints23            while (!dq.isEmpty() && (i - dq.peekFirst() > maxBoxes || prefixWeight[i] - prefixWeight[dq.peekFirst()] > maxWeight)) {24                dq.pollFirst();25            }26 27            int bestJ = dq.peekFirst();28            // dp[i] = (2 + prefixChanges[i-1]) + g[bestJ]29            // g[bestJ] = dp[bestJ] - prefixChanges[bestJ-1] (if we define it that way)30            // Let's use the direct formula: dp[i] = dp[bestJ] + cost(bestJ, i-1)31            dp[i] = dp[bestJ] + 2 + (prefixChanges[i - 1] - (bestJ > 0 ? prefixChanges[bestJ - 1] : 0));32            // This is getting complex. Let's use the g(j) formulation which is cleaner.33            // dp[i] = g[bestJ] + 2 + prefixChanges[i-1]34            // Let's redefine g(j) = dp[j] + (2 - prefixChanges[j-1])35            // Let's stick to the math: dp[i] = (2 + prefixChanges[i-1]) + min(dp[j] - prefixChanges[j])36            // Let's use prefixChanges of size n+1 for simpler indexing37            int[] pChanges = new int[n + 1];38            for(int k=0; k<n-1; ++k) {39                pChanges[k+2] = pChanges[k+1] + (boxes[k][0] != boxes[k+1][0] ? 1 : 0);40            }41            // cost(j, i-1) = 2 + pChanges[i] - pChanges[j+1]42            // dp[i] = min(dp[j] + 2 + pChanges[i] - pChanges[j+1])43            // dp[i] = 2 + pChanges[i] + min(dp[j] - pChanges[j+1])44            // This is the optimization target.45            long[] costToOptimize = new long[n + 1];46            costToOptimize[0] = 0; // dp[0] - pChanges[1] = 047            dq.clear();48            dq.offerLast(0);49 50            for(int k=1; k<=n; ++k) {51                while(!dq.isEmpty() && (k - dq.peekFirst() > maxBoxes || prefixWeight[k] - prefixWeight[dq.peekFirst()] > maxWeight)) {52                    dq.pollFirst();53                }54                dp[k] = costToOptimize[dq.peekFirst()] + 2 + pChanges[k];55                costToOptimize[k] = dp[k] - pChanges[k+1 > n ? k : k+1];56                while(!dq.isEmpty() && costToOptimize[dq.peekLast()] >= costToOptimize[k]) {57                    dq.pollLast();58                }59                dq.offerLast(k);60            }61            return (int)dp[n];62        }63    }

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ]; } }

1class Solution:2    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]

1class Solution {2public:3  int boxDelivering(vector<vector<int>> &boxes, int portsCount, int maxBoxes,4                    int maxWeight) {5    int n = boxes.size();6    long ws[n + 1];7    int f[n + 1];8    int cs[n];9    ws[0] = cs[0] = f[0] = 0;10    for (int i = 0; i < n; ++i) {11      int p = boxes[i][0], w = boxes[i][1];12      ws[i + 1] = ws[i] + w;13      if (i < n - 1)14        cs[i + 1] = cs[i] + (p != boxes[i + 1][0]);15    }16    deque<int> q{{0}};17    for (int i = 1; i <= n; ++i) {18      while (!q.empty() &&19             (i - q.front() > maxBoxes || ws[i] - ws[q.front()] > maxWeight))20        q.pop_front();21      if (!q.empty())22        f[i] = cs[i - 1] + f[q.front()] - cs[q.front()] + 2;23      if (i < n) {24        while (!q.empty() && f[q.back()] - cs[q.back()] >= f[i] - cs[i])25          q.pop_back();26        q.push_back(i);27      }28    }29    return f[n];30  }31};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem