Delivering Boxes from Storage to Ports

Hard
1622.

Delivering Boxes from Storage to Ports

Delivering Boxes from Storage to Ports is a hard coding problem on arrays, dynamic programming and prefix sum, asked in Amazon interviews.

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:

  1. At storage, load the next few waiting boxes (in order), within both limits.
  2. 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.
  3. 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^5
  • 1 <= portsCount, maxBoxes, maxWeight <= 10^5
  • 1 <= port_i <= portsCount
  • 1 <= weight_i <= maxWeight
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} boxes
 * @param {number} portsCount
 * @param {number} maxBoxes
 * @param {number} maxWeight
 * @return {number}
 */
var boxDelivering = function(boxes, portsCount, maxBoxes, maxWeight) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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:

  1. At storage, load the next few waiting boxes (in order), within both limits.
  2. 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.
  3. 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^5
  • 1 <= portsCount, maxBoxes, maxWeight <= 10^5
  • 1 <= port_i <= portsCount
  • 1 <= weight_i <= maxWeight

Hints for Delivering Boxes from Storage to Ports

  1. Hint 1

    A load of boxes j..i-1 always costs 2 plus the number of adjacent pairs inside it that go to different ports. So dp[i] = min(dp[j] + 2 + changes(j, i-1)) over loads that fit.

  2. Hint 2

    Let c[k] count port changes among the first k boxes. Then changes(j, i-1) = c[i] - c[j+1], and the term to minimise is dp[j] - c[j+1], which does not depend on i.

  3. Hint 3

    The valid j form a sliding window (the box and weight limits only ever push its left end forward), so keep a monotonic deque of j ordered by dp[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

  1. Build prefix weights W[k] and change counts c[k] (c[k] = number of t in [1, k-1] with port[t] != port[t-1]).
  2. dp[0] = 0. For i = 1..n, the last load is boxes j..i-1 with i - j <= maxBoxes and W[i] - W[j] <= maxWeight; its cost is dp[j] + c[i] - c[j+1] + 2.
  3. Keep a deque of candidate j with increasing dp[j] - c[j+1]. Before computing dp[i], drop front entries that violate the box or weight limit; the front is the best j.
  4. After computing dp[i] (for i < n), push i, first popping back entries whose key is not smaller.
  5. 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 <= maxWeight and maxBoxes >= 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