Taro Logo

Delivering Boxes from Storage to Ports

Hard
Nutanix logo
Nutanix
1 view
Topics:
ArraysDynamic ProgrammingSliding Windows

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

  • ports​​i is the port where you need to deliver the ith box and weightsi is the weight of the ith 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 <= 105
  • 1 <= portsCount, maxBoxes, maxWeight <= 105
  • 1 <= ports​​i <= portsCount
  • 1 <= weightsi <= maxWeight
Try coding it in LeetCodeLeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the constraints on the number of boxes (`boxes.length`), the port values (`port`), and the weight values (`weight`)? What is the maximum value for `maxBoxes` and `maxWeight`?
  2. Is it possible for a box to have a weight of 0? Is it possible for `maxWeight` to be 0?
  3. If it's impossible to deliver all the boxes within the given constraints, what value should I return?
  4. Are the port numbers guaranteed to be within a specific range or are they arbitrary integers?
  5. If multiple valid solutions exist, should I return any one of them, or is there a specific criteria (e.g., minimizing the number of individual boxes across all trips) for choosing between solutions?

Brute Force Solution

Approach

The brute force method aims to find the best way to ship boxes from a storage area to different ports. It essentially tries every possible combination of how to group the boxes being sent together in shipments. It then evaluates each combination to find the cheapest one.

Here's how the algorithm would work step-by-step:

  1. Consider each box individually as its own shipment.
  2. Next, consider every possible pair of boxes being shipped together.
  3. Then, consider every possible group of three boxes, then four, and so on, until all boxes are in one big shipment.
  4. For each of these groupings, calculate the cost of shipping them together based on the number of port changes.
  5. Keep track of the cost for each possible combination of shipments.
  6. Finally, after exploring all possibilities, select the combination of shipments that results in the lowest overall cost.

Code Implementation

def delivering_boxes_brute_force(ports):
    number_of_boxes = len(ports)
    minimum_cost = float('inf')

    # Iterate through all possible shipment combinations.
    for i in range(1 << (number_of_boxes - 1)):
        shipments = []
        current_shipment = [ports[0]]

        for j in range(number_of_boxes - 1):
            # Determine if a new shipment starts at this box.
            if (i >> j) & 1:
                shipments.append(current_shipment)
                current_shipment = [ports[j + 1]]
            else:
                current_shipment.append(ports[j + 1])

        shipments.append(current_shipment)

        current_cost = 0
        for shipment in shipments:
            # Calculate the cost for each shipment.
            port_changes = 0
            for k in range(len(shipment) - 1):
                if shipment[k] != shipment[k+1]:
                    port_changes += 1
            current_cost += port_changes

        # Find and save lowest shipping cost across all combos.
        minimum_cost = min(minimum_cost, current_cost)

    return minimum_cost

Big(O) Analysis

Time Complexity
O(2^n) – The brute force approach iterates through all possible combinations of box groupings. For each box, it can either be in its own shipment or grouped with other boxes. This creates 2 choices for each of the n boxes, leading to 2^n possible combinations. Calculating the cost for each combination then takes O(n) time to iterate through and compute the port changes. Therefore, the overall time complexity becomes O(n * 2^n). Since exponential complexity dominates polynomial factors, it can be simplified to O(2^n).
Space Complexity
O(2^N) – The algorithm explores all possible combinations of box groupings. This implies generating all possible subsets of the boxes. Representing these subsets requires storing intermediate results for each combination considered. In the worst case, it stores all possible combinations which is 2^N, where N is the number of boxes. Therefore, the auxiliary space required grows exponentially with the number of boxes.

Optimal Solution

Approach

The most efficient way to solve this problem is to use a technique called dynamic programming. Instead of recalculating the cost of delivering boxes to a port multiple times, we store and reuse the results of previously computed subproblems. This avoids redundant work and significantly speeds up the process.

Here's how the algorithm would work step-by-step:

  1. Start from the end: Consider the last delivery you need to make.
  2. Figure out the cost of making just that last delivery by itself.
  3. Now, work backwards: Think about the second-to-last delivery. What's the best way to combine it with the last delivery (either together or separately)? Store the minimum cost.
  4. Keep moving backwards, delivery by delivery. For each one, decide if it's cheaper to make it in the same group as the next deliveries, or start a new delivery group. Always save the cheapest cost you find.
  5. When you get to the very first delivery, you'll have figured out the absolute best way to group all the deliveries together, and the total minimum cost of the whole operation will be known.

Code Implementation

def delivering_boxes(boxes, max_boxes, max_weight_per_trip):    number_of_boxes = len(boxes)
    dp_table = [0] * (number_of_boxes + 1)

    for i in range(number_of_boxes - 1, -1, -1):
        min_cost = float('inf')
        current_weight = 0
        boxes_count = 0

        # Iterate to find optimal grouping, minimizing cost
        for j in range(i, number_of_boxes):
            boxes_count += 1
            current_weight += boxes[j][0]

            # Check if constraints are violated
            if boxes_count > max_boxes or current_weight > max_weight_per_trip:
                break

            cost = 2 + dp_table[j + 1]

            # Add cost to switch ports if needed
            if j + 1 < number_of_boxes and boxes[i][1] != boxes[j + 1][1]:
                cost += 1

            min_cost = min(min_cost, cost)

        dp_table[i] = min_cost

    # Result is stored at the beginning of DP table
    return dp_table[0]

Big(O) Analysis

Time Complexity
O(n) – The dynamic programming solution iterates backward through the input array of boxes, which has a size of n. For each box, it considers the cost of delivering it either separately or together with subsequent boxes. This involves a constant amount of work for each box, calculating the cost and updating the minimum cost. Therefore, the time complexity is directly proportional to the number of boxes, resulting in O(n).
Space Complexity
O(N) – The dynamic programming solution described stores the minimum cost calculated for each delivery from the end. This implies the use of an auxiliary array or data structure, such as a list, to store these intermediate results for each of the N deliveries. Therefore, the space required grows linearly with the number of deliveries, N. This auxiliary data structure is used to avoid recomputation and find the overall optimal solution. The space complexity is thus O(N).

Edge Cases

CaseHow to Handle
Empty boxes arrayReturn 0 since no trips are needed when there are no boxes.
maxBoxes or maxWeight is zeroReturn -1 since no boxes can be loaded, making delivery impossible.
A single box exceeds maxWeightReturn -1 since a single box cannot be transported within the weight constraint.
All boxes have the same portThe dynamic programming solution should correctly calculate trips without being affected by similar port values.
All boxes have different portsThe cost calculation for different ports must still be performed.
Large input size (large number of boxes)Ensure the DP array is not excessively large to avoid memory issues and optimize time complexity.
Integer overflow when calculating cumulative weights.Use long data type for cumulative weights to prevent potential overflow.
Boxes are already sorted optimallyDP solution should naturally find the optimal solution even when boxes are well organized.
Taro Footer Icon
Taro Footer Logo
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
Explore TrendingLayoffsPerformance Improvement PlanSystem DesignInterpersonal CommunicationTech Lead
ProductBecome An AffiliateGreat DiscussionsPerksTopics
CompanyBlogPrivacy PolicyTerms & ConditionsSupport
Taro iOS appTaro Android app
LinkedIn IconTwitter IconYouTube Icon
Copyright © Taro