Delivering Boxes from Storage to Ports: Sliding Window DP

LeetCode Delivering Boxes from Storage to Ports (Problem 1687) asks you to deliver n boxes to ports using the minimum total cost. Each box has a destination port and a weight. You load consecutive boxes onto a ship, deliver them in order, then return to storage. The challenge is figuring out how to partition the boxes into trips to minimize the overall cost.

The problem

You have n boxes lined up in a row. Each box i is described by boxes[i] = [port_i, weight_i]. Your ship can carry at most maxBoxes boxes and at most maxWeight total weight per trip. Each trip works like this: you leave storage, deliver the loaded boxes to their ports one by one (in order), and return to storage.

The cost of a single trip is the number of times the destination port changes between consecutive boxes in that trip, plus 2 (one for leaving storage, one for returning). Your goal is to find the minimum total cost across all trips.

For example, if a trip delivers boxes going to ports [1, 2, 1], the port changes twice (1 to 2, then 2 to 1), so the trip costs 2 + 2 = 4.

The brute force approach

You could try all possible ways to partition the boxes into consecutive trips. For each partition, check that every trip respects the maxBoxes and maxWeight constraints, then sum up the trip costs. But the number of ways to partition n items into consecutive groups is exponential, so this approach is far too slow for any reasonable input size.

The key insight

Define dp[i] as the minimum cost to deliver the first i boxes (boxes 0 through i-1). For each i, you want to find the best starting position j for the last trip, where that trip covers boxes j through i-1. The trip must satisfy i - j is at most maxBoxes and the total weight of boxes j through i-1 is at most maxWeight.

The cost of a trip from box j to box i-1 is the number of port changes in that range, plus 2. To compute port changes in any range efficiently, precompute a prefix array diff where diff[i] counts the total number of port changes from box 0 to box i. Then port changes from box j to box i-1 equals diff[i-1] - diff[j].

The DP recurrence becomes: dp[i] = min over valid j of (dp[j] + diff[i-1] - diff[j] + 2).

Rearranging, you want to minimize dp[j] - diff[j] over the valid window of j values, then add diff[i-1] + 2. This is a classic sliding window minimum, which you can solve with a monotonic deque in O(1) amortized time per step.

Step-by-step walkthrough

The walkthrough uses boxes = [[1,1],[2,1],[1,1],[1,1],[3,1],[3,1]] with maxBoxes = 3 and maxWeight = 3. The diff array tracks cumulative port changes. At each step, the sliding window ensures we only consider valid starting positions, and the deque maintains the optimal j that minimizes dp[j] - diff[j]. The final answer is dp[6] = 7.

The code

def boxDelivering(boxes, portsCount, maxBoxes, maxWeight):
    n = len(boxes)
    diff = [0] * n
    for i in range(1, n):
        diff[i] = diff[i - 1] + (1 if boxes[i][0] != boxes[i - 1][0] else 0)
    dp = [0] * (n + 1)
    from collections import deque
    dq = deque()
    dq.append(0)
    weight = 0
    j = 0
    for i in range(1, n + 1):
        weight += boxes[i - 1][1]
        while i - j > maxBoxes or weight > maxWeight:
            weight -= boxes[j][1]
            j += 1
        while dq and dq[0] < j:
            dq.popleft()
        dp[i] = dp[dq[0]] - diff[dq[0]] + diff[i - 1] + 2
        while dq and dp[dq[-1]] - diff[dq[-1]] >= dp[i] - diff[i]:
            dq.pop()
        dq.append(i)
    return dp[n]

The diff array is the prefix count of port changes: diff[i] tells you how many times the port changes between consecutive boxes from index 0 up to index i. The DP transition for dp[i] picks the best j in the valid window (constrained by maxBoxes and maxWeight) that minimizes dp[j] - diff[j]. Adding diff[i-1] + 2 gives the total cost. The deque stores indices in increasing order of dp[j] - diff[j], so the front of the deque is always the optimal choice. When the window slides forward (because j must increase), stale entries get popped from the front. When a new dp[i] is computed, entries at the back that are worse get popped before appending i.

Complexity analysis

Each index enters and leaves the deque at most once, giving amortized O(1) per step. The prefix diff array and the dp array both take O(n) space.

The building blocks

Prefix sums for range queries

The diff array is a prefix sum of port changes. diff[i] = diff[i-1] + (1 if boxes[i] and boxes[i-1] go to different ports, else 0). To find the number of port changes in a subarray from index j to index i, you compute diff[i] - diff[j]. This is the same idea as using a prefix sum array to answer range sum queries in O(1), just applied to a binary indicator (did the port change?).

Monotonic deque optimization

The DP recurrence asks for the minimum of dp[j] - diff[j] over a sliding window of valid j values. A monotonic deque maintains a list of candidate indices where dp[j] - diff[j] is non-decreasing. When you add a new candidate, you pop from the back anything that is worse (greater or equal). The front of the deque always holds the current minimum. This pattern appears in many DP problems where the transition involves a sliding range minimum or maximum.

Sliding window constraints

Two constraints define the valid window: the number of boxes (i - j is at most maxBoxes) and the total weight (sum of weights from j to i-1 is at most maxWeight). As i increases, j can only move forward, never backward. This monotonicity is what makes the sliding window approach work. You maintain a running weight sum and increment j whenever either constraint is violated.

Edge cases

All boxes go to the same port. Every trip has zero port changes, so each trip costs exactly 2. The optimal strategy is to pack as many boxes as possible into each trip, minimizing the number of trips.

Single box. The answer is always 2 (leave storage, deliver, return).

maxBoxes = 1. Each box gets its own trip. The answer is 2 * n, since every trip has zero port changes and costs 2.

Weight exactly at limit. The sliding window handles this correctly. When adding box i-1 causes the weight to exceed maxWeight, the left pointer j advances until the weight drops back within the limit.

All boxes have different ports. Every consecutive pair causes a port change. The diff array increases by 1 at every index, and the deque optimization is especially valuable here since the trip costs are high and finding the right partition matters more.

From understanding to recall

This problem has a three-layer structure, and each layer builds on the previous one. First, the DP recurrence: dp[i] is the minimum cost to deliver the first i boxes, and you choose where the last trip starts. Second, the prefix port change array: it lets you compute the cost of any trip in O(1). Third, the monotonic deque: it finds the optimal starting position for the last trip in amortized O(1).

When reviewing this problem, focus on how these three pieces connect. The prefix array transforms the DP transition from "count port changes in a range" to "subtract two prefix values." The deque then exploits the structure of dp[j] - diff[j] to avoid scanning the entire window. If you can reconstruct why each layer is needed and how they combine, you have a strong template for many other deque-optimized DP problems.

Related posts

• Sliding Window Maximum - The classic monotonic deque problem that builds the foundation for deque-optimized DP.
• Minimum Number of K Consecutive Bit Flips - Another problem combining sliding windows with greedy/DP decisions over consecutive elements.
• Jump Game II - Greedy partitioning of an array into segments with minimum cost, sharing the "how far can this segment extend" structure.