Capacity to Ship Packages - Leetcode 1011 - Python

Solving leetcode 1011 - capacity to ship packages, today's daily leetcode problem on february 21.

0:00 - Read the problem
1:15 - Drawing Explanation
8:10 - Coding Explanation

leetcode 1011

#neetcode #leetcode #python

[Avuvos]

I think its worth explaining why Binary Search actually works in this case, and the reason is that our "canShip" function is monotonic, which means if we found some weight that doesn't fit, it for sure means that every weight below that also won't fit, and same for if we found a weight that fits, no need to check any values above that weight.

Also there is no reason to set res = min(res, cap), it is enough to just set res = cap, since it will always update it if we entered that if, again because of the monotonic attribute.

[Lucas-hrmj]

I did not spot the binary search right away, gotta improve pattern recognition, it was very straightforward after I realized it.

[souravdhar]

you know you are legend when remember questions by their leetcode no.😆

[infiniteloop]

first comment! I thought this would never happen! Neetcode famous!

[julianomoura]

Well, a nice thing to notice is that you dont need the conditional attribution `res = min(res, cap)`. Since the binary search is looking for deacrising valid values, every time you find a possible solution it will be better than the previous one, so you can just do `res = cap`.

[doronbaruch]

I love your solution. Thank you for making those. Those videos are super valuable. Nit tiny comment, in 6:45 you said the res value is 9 but it's 10 at that point. But this is very minor. (-;

[AP-ehgr]

1:19 good call, 1 ship over 5 days is the same as 5 ships carrying stuff in one day

[CostaKazistov]

Right (upper bound) can be optimised even further with walrus operator in Python:
right = min(total_weight := sum(weights), total_weight // days + left)

This will improve performance quite a bit.

[DevChannel-bi]

Very nice and clear explanation, thanks!

[quirkyquester]

a very tricky problem here, thank you for the video!

[Jia-Tan]

While solving this I was debating whether to set my upper bound to the sum of the weights or just the maximum weight allowed (500)
Doing the same algorithm with lower bound as 1 and upper bound as 500 gives consistently faster runtime since we didn't need to check all the weights beforehand to get those values, and since we decrease the problem size by half on every iteration, it still finds the answer pretty quickly.

That said I'm not sure this would be a universally better approach, just worked slightly better under these circumstances/test cases. Would love to hear others thoughts!

[Lulit]

Solved this with the same idea, but your code was much more elegant

[ivanmiroshnichenko]

Another observation. If you get len(weights) / days that will be min chunk in size that can be loaded to ship to get to load ship with the same chunk size every day. Hence we can get max value for chunk of that size by using sliding window so it would be o(n) time and at the same time we can get max value in weights. Upper bound is max sum for chunk and min is max element in weights. This is a small optimization. Code gets longer in this case ofc

[nw]

You can also implement a Binary Search in the canShip() function by using a prefix sum array and cutting the left part of it that you can fit in one ship. That is O(n) in worst case scenario, but I think it should be O(log(n)) for the average/best case. Though, this solution is 30% slower on LeetCode.

[ksankethkumar]

Hello, I feel I'm strong in DSA problems, but i am unable to figure out ways to solve new questions or how to approach them? What would be the issue and how to get through it?

[nikhilgoyal]

self note for why ships = 1 ( and not 0 when initializing) is because if the ship is not filled completely - still one ship will be required and then extrapolate it to if the second ship is not filled completely.

[eliott]

What whiteboard software do you use to draw on the screen?

[varunaggarwal]

c++ code:
class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
int n = weights.size();
if(n<days){
return -1;
}
int left = INT_MIN;
int right =0;
for(int i=0;i<n;i++){
left=max(left, weights[i]);
right+=weights[i];
}
int ans=-1;
while(left<right){
int mid=(left+right)>>1;

if(isvalid(weights, n, mid, days)){
right=mid;
ans=mid;
}
else{
left=mid+1;
}



}
return left;
}

bool isvalid(vector<int> weights, int n, int mid, int k){
int ships=1;
int sum=0;


for(int i=0;i<n;i++){
sum+=weights[i];
if(sum>mid){
ships++;
sum=weights[i];
}
if(ships>k){
return false;
}

}

return true;
}


};

[def__init]

Perhaps this was obvious but why does the problem not explicitly state that a package can NOT be split between ships??
This is how we determine the lower bound to be max(weights) but it’s not immediately clear from problem description imo, at least for me lol

[srinivasanbalan]

Thanks for the video. I have a question. What if the capacity is 8 so that [1 2 4] and [3 5] can be handled effectively with the minimum capacity. There is no hard rule that products can be shipped only in the order of given weights. If we solve this using DP, we get to see the minimum capacity required is 8 only for two ships. Any thoughts on this?