How do you solve Delivering Boxes from Storage to Ports on LeetCode?

Delivering Boxes from Storage to Ports (LeetCode #1687) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Maximize the number of boxes per trip

What is the brute force solution for Delivering Boxes from Storage to Ports?

The brute force approach for Delivering Boxes from Storage to Ports is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves simulating every possible loading of boxes and calculating the number of trips required for each configuration. This method is straightforward but inefficient, as it checks all combinations of boxes. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Delivering Boxes from Storage to Ports?

Think about edge cases, such as when all boxes fit in one trip Explain your thought process clearly while coding Practice similar problems to recognize patterns

What are common mistakes when solving Delivering Boxes from Storage to Ports?

Not resetting the current weight and boxes after returning to storage Failing to account for the final return trip to storage

#1687

Delivering Boxes from Storage to Ports

Hard

ArrayDynamic ProgrammingSegment TreeQueueHeap (Priority Queue)Prefix SumMonotonic QueueGreedySliding Window

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach uses a greedy strategy combined with a sliding window technique to efficiently manage the loading of boxes while adhering to the constraints. This reduces the number of trips by maximizing the number of boxes delivered in each trip.

⚙️

Algorithm

4 steps

1Step 1: Initialize a trip counter and variables for current weight and boxes.
2Step 2: Use a sliding window to track the boxes that can be loaded without exceeding maxBoxes and maxWeight.
3Step 3: For each box, check if it can be added to the current load. If it can't, increment the trip counter and reset the load.
4Step 4: After processing all boxes, ensure to count the return trip to storage.

solution.py23 lines

1# Full working Python code
2
3def boxDelivering(boxes, portsCount, maxBoxes, maxWeight):
4    trips = 0
5    currentWeight = 0
6    currentBoxes = 0
7    lastPort = -1
8    n = len(boxes)
9    i = 0
10    while i < n:
11        if currentBoxes < maxBoxes and currentWeight + boxes[i][1] <= maxWeight:
12            currentWeight += boxes[i][1]
13            if lastPort != boxes[i][0]:
14                trips += 1  # Trip to a new port
15                lastPort = boxes[i][0]
16            currentBoxes += 1
17            i += 1
18        else:
19            trips += 1  # Return trip to storage
20            currentWeight = 0
21            currentBoxes = 0
22    trips += 1  # Final return trip to storage
23    return trips

ℹ

Complexity note: The time complexity is O(n) because we only make a single pass through the boxes, checking the constraints as we go, which is much more efficient than the brute force approach.

1Maximize the number of boxes per trip
2Keep track of the last port to avoid unnecessary trips

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.