Delivering Boxes from Storage to Ports - Practice Coding Problems

Delivering Boxes from Storage to Ports - Problem

Array Dynamic Programming Segment Tree Queue Heap (Priority Queue) Prefix Sum Monotonic Queue Hard

You have the task of delivering boxes from storage to their ports using only one ship. The ship has limits on the number of boxes and total weight it can carry.

You are given an array boxes where boxes[i] = [portsi, weighti], and three integers portsCount, maxBoxes, and maxWeight.

portsi is the port where you need to deliver the ith box
weightsi is the weight of the ith box
portsCount is the number of ports
maxBoxes and maxWeight are the ship's capacity limits

The boxes must be delivered in the given order. The ship follows these steps:

Take boxes from the queue without violating maxBoxes and maxWeight constraints
For each loaded box in order, make a trip to deliver it (if already at the correct port, no trip needed)
Return to storage to take more boxes

The ship must end at storage after all deliveries. Return the minimum number of trips needed.

Input & Output

Example 1 — Basic Case

$ Input: boxes = [[1,1],[4,6],[1,2],[2,7],[3,2]], portsCount = 3, maxBoxes = 4, maxWeight = 6

› Output: 6

💡 Note: Trip 1: Take boxes [1,1],[4,6] but weight exceeds. Take only [1,1], deliver to port 1, return. Trip 2: Take [4,6], deliver to port 4, return. Trip 3: Take [1,2],[2,7] but weight exceeds. Take [1,2], deliver to port 1, return. Trip 4: Take [2,7], deliver to port 2, return. Trip 5: Take [3,2], deliver to port 3. Total: 6 trips.

Example 2 — Efficient Grouping

$ Input: boxes = [[1,2],[3,3],[1,1]], portsCount = 3, maxBoxes = 3, maxWeight = 6

› Output: 4

💡 Note: Trip 1: Take all boxes [1,2],[3,3],[1,1] (weight = 6, boxes = 3). Deliver to port 1, then port 3, then port 1 again. Total: 4 trips (1→3→1→storage).

Example 3 — Single Box Per Trip

$ Input: boxes = [[1,4],[2,5]], portsCount = 2, maxBoxes = 1, maxWeight = 10

› Output: 4

💡 Note: Trip 1: Take [1,4], deliver to port 1, return. Trip 2: Take [2,5], deliver to port 2. Total: 4 trips.

Constraints

1 ≤ boxes.length ≤ 10⁵
1 ≤ portsCount, boxes[i][0] ≤ 10⁵
1 ≤ boxes[i][1] ≤ 10⁵
1 ≤ maxBoxes, maxWeight ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Boxes with [port, weight], ship constraints maxBoxes, maxWeight

Process

Group consecutive boxes optimally, count unique ports per group

Output

Minimum total trips needed (2×ports per group, except last)

Key Takeaway

🎯 Key Insight: Use DP to optimally group consecutive boxes, minimizing total trips by balancing load sizes with unique port counts per trip.

Asked in

G Google 15 a Amazon 25 M Microsoft 12

The key insight is to use dynamic programming to find the optimal way to group consecutive boxes into ship loads. Each load visits unique ports (counting as 2×ports trips for round-trip, except the last load). Best approach uses bottom-up DP with prefix sums. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Dynamic Programming	O(n²)	O(n)	Try all possible ways to group consecutive boxes and pick the minimum trips
Optimized Dynamic Programming	O(n²)	O(n)	Use DP with prefix sums and deque optimization for faster computation

Brute Force Dynamic Programming — Algorithm Steps

For each position i, try all valid ending positions j
Check if boxes[i:j+1] fit in ship constraints
Recursively solve for remaining boxes
Take minimum across all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Current Position

Start from position i, try all valid ending positions

Check Constraints

Ensure box count ≤ maxBoxes and weight ≤ maxWeight

Calculate Trips

Count unique ports × 2 (round trip) + recursive solve

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int memo[1001];
int memoSet[1001];

int dp(int start, int boxes[][2], int n, int maxBoxes, int maxWeight) {
    if (start >= n) return 0;
    
    if (memoSet[start]) return memo[start];
    
    int minTrips = INT_MAX;
    int weight = 0;
    int portsVisited[101] = {0};
    int portCount = 0;
    
    int end = (start + maxBoxes < n) ? start + maxBoxes : n;
    
    for (int i = start; i < end; i++) {
        weight += boxes[i][1];
        if (weight > maxWeight) break;
        
        if (!portsVisited[boxes[i][0]]) {
            portsVisited[boxes[i][0]] = 1;
            portCount++;
        }
        
        int tripsForLoad = portCount * 2;
        if (i == n - 1) tripsForLoad = portCount;
        
        int totalTrips = tripsForLoad + dp(i + 1, boxes, n, maxBoxes, maxWeight);
        if (totalTrips < minTrips) minTrips = totalTrips;
    }
    
    memo[start] = minTrips;
    memoSet[start] = 1;
    return minTrips;
}

int solution(int boxes[][2], int n, int portsCount, int maxBoxes, int maxWeight) {
    memset(memoSet, 0, sizeof(memoSet));
    return dp(0, boxes, n, maxBoxes, maxWeight);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small inputs
    int boxes[100][2];
    int n = 0;
    
    char *ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            boxes[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            boxes[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            n++;
        }
        ptr++;
    }
    
    int portsCount, maxBoxes, maxWeight;
    scanf("%d %d %d", &portsCount, &maxBoxes, &maxWeight);
    
    int result = solution(boxes, n, portsCount, maxBoxes, maxWeight);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each position, we try all possible endings, leading to O(n²) states

⚠ Quadratic Growth

Space Complexity

O(n)

Memoization table stores results for n positions

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler