Capacity To Ship Packages Within D Days Leetcode Solution  

Difficulty Level Medium
Frequently asked in Amazon
algorithms Array Binary Search coding Interview interviewprep LeetCode LeetCodeSolutions

Problem statement  

In the problem ” Capacity To Ship Packages Within D Days,” we have packets in port A that must be transferred to port B in D days.

we are given a weights array that contains the weight of each packet and the number of days in which we need to transfer the packets. Our task is to find the minimum load capacity of the ship to be used to transfer packets from port A to port B in D days.

leetcode solution to capacity to ship packages within D daysPin

Example

weights = [1,2,3,4,5,6,7,8,9,10], D = 5
15

Explanation: The ship will transfer the packets in the following way:

Please click Like if you loved this article?

First-Day : 1,2,3,4,5

Second-Day 2: 6,7

Third-Day 3: 8

Fourth-Day 4: 9

Fifth-Day 5: 10

In this way, the minimum load capacity of the ship should be 15 to transfer all packets in 5 days.

Approach for Capacity To Ship Packages Within D Days Leetcode Solution  

The first and the most important thing to solve this problem is to bring out observations. Here are a few observations for our search interval:

  1. The load capacity of the ship should be at least equal to the packet having the maximum weight that is max(weights). let’s name it as Start.
  2. We can limit the maximum capacity of the ship to the sum of the weight of all the packets that is sum(weights). let’s name it as End.
See also
Best Time to Buy and Sell Stock  II Leetcode Solution

Now we have our search interval. Suppose the size of the interval is Length and the number of packets is n.  The naive approach could be to check for each value in the interval if that load capacity can transfer the packets successfully in D days and pick the minimum out of them. The time complexity for the naive approach will be Length*n.

We can improve the time complexity by using Binary Search in place of Linear Search.

The time complexity using the Binary Search approach will be log(Length)*n.

Implementation

C++ code for Capacity To Ship Packages Within D Days Leetcode Solution

#include <bits/stdc++.h>
using namespace std; 
    int shipWithinDays(vector<int>& weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4,5,6,7,8,9,10}; 
 int d=5;                               

 cout<<shipWithinDays(arr,d)<<endl;
 return 0;
}
15

Java code for Capacity To Ship Packages Within D Days Leetcode Solution

public class Tutorialcup {
    public static int shipWithinDays(int[] weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = Math.max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,4,5,6,7,8,9,10}; 
     int d=5; 
    int ans= shipWithinDays(arr,d);
    System.out.println(ans);
  }
}
15

Complexity Analysis of Capacity To Ship Packages Within D Days Leetcode Solution  

Time complexity

The time complexity of the above code is O(n*log(Length)) because we are traversing the weight array log(Length) times. Here n and Length are the numbers of packets and size of the search interval respectively.

See also
Find Sum of all unique sub-array sum for a given array

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store the answer.

References

Please click Like if you loved this article?