BS-15. Capacity to Ship Packages within D Days
Vložit
- čas přidán 22. 06. 2023
- Problem Link: bit.ly/43QDpdG
Notes/C++/Java/Python codes:
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
0:00 Introduction of Course
solved it on my own , woohoo confidence is just sky rocketing !! thank you striver
bhaiya i have done the last two problems on my own without watching your solution and now i am gaining a little bit of confidence that i can also do.... it is not that i haven't done any problem on my own but it was after completing your playlist of that topic and then doing other problem of that topic, but it is the first time i am doing this before completing this playlist of binary search,,, thank you bhaiya , you teaching style is just awesome😍😇😇
gawd
dude exactly same, i was also able to solve this one and the last one on my own. this happened for the first time!!
@@arujgarg7267 Exactly same... Solved this and previous 2 problems on my own
One more thing that should be added into the question is that the weights need to shipped in order. I think if we are to club the minimum and the maximum weights together then 11 would be the answer for this [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Days = 5
Ikr, right now the question seems more like binary search over series of knapsacks instead of contiguous sums
yup, i was literally thinking the same thing, i thought if i only take consecutive days i might get error in leetcode.
The way you explain and write the code so clearly is what is so unique about you. Clearly understood, thanks!
bro this is one of the best cheat sheet.
the way you split each patterns into sub patterns is great
Would be great if you continue to find sub patterns within existing patterns
SALUTE HAI BHAI..!! kya smjhaya hai ..itna easy logic!!... blown away! Thank you rahega
Crystal clear explanation striver... Clearly understood everything...Thanks a lot for this awesome series.
aapki videos shuru majboori mei kiye the,
lekin ab maza aane laga hai :)
sammmmee😂
man..even this one i coded down myself...understanding the previous ones...thanks bhai
❤understood, next level lecture , this is what the tier 3 students wish to listen in classroom
thank u striver bhaiyaa!you made divide and conquer a cakewalk! this ecstatic feeling is so morale boosting as i did this problem by myself in a single go under your guidance ! much love
Understood! Super excellent explanation as always, thank you very much for your effort!!
Was able to solve this on my own. This question is similar to minimum days to make m bouquets. Thanks a tonne, Striver !!!!
*Completed now, thanks for such lovely content.*
superb explanation, 80% coded it myself, tysmm
I watched 5 videos and was trying to understand this for last 3 days, but the way you explained it has become like cutting butter for me now..thanks a lot
Can u share where were doing this problem, was it a platform other than leetcode ? Kindly share
Wow...the portrait of the ship is so good 😃
wow man, i could able to solve this on my own. i am watching this because i just wanna see your explination, i am following your playlist, learning in a structure and doing similar problem really helps in undertanding the concept, thank man. also after solving koko banana problem, solving prev problem in this playlist find the smallest divisor, really cake walk.
tha't it, tho i don't comment that much, you are helping many ppl like me. thanks for doing all the work.
Thanks man! you make the code look so simple, Idk why I end up writing a long and complex brute force code even though it works..
Understood
Thank You striver for such an amazing explanation
mistake at 15:03 it will come to 31 not 23, but its ok. under stood.
agree
Thank You Striver understood everything🙂
sorry to say but studying DSA with you and LOVE sir combined is just better than best
love babbar?
@@ajaynaik2480 yaaa
Where are you placed now??
I was able to code in less than 7 mins (thala for a reason....naah, obv u the reason).....thanks a lot.
Understood Very Well!
Man, you're legend🤓. Thanks
Understood! Thanks :)
slight improvement, the max can also be sum(weights)-days+1. This is because in worst case you can ship the item with max weight on day 1, then remaining items combination on each days
- [00:17](czcams.com/video/Mde2q7GFCrw/video.html) The problem is about finding the minimum capacity needed to ship packages within a given number of days.
- [01:49](czcams.com/video/Mde2q7GFCrw/video.htmlm49s) An example is given where if the ship's capacity is 100, all packages can be shipped in one day.
- [03:22](czcams.com/video/Mde2q7GFCrw/video.htmlm22s) It is demonstrated that a capacity of 10 leads to shipping taking more than the given number of days.
- [04:20](czcams.com/video/Mde2q7GFCrw/video.htmlm20s) Increasing the capacity to 15 allows shipping all packages within the given days.
- [06:11](czcams.com/video/Mde2q7GFCrw/video.htmlm11s) The answer must be between the maximum weight of a product and the sum of all weights.
- [08:01](czcams.com/video/Mde2q7GFCrw/video.htmlm1s) A function is described to find the number of days required to ship with a given capacity.
- [12:32](czcams.com/video/Mde2q7GFCrw/video.html2m32s) The initial solution has a time complexity of O(N^2) due to linear search.
- [13:54](czcams.com/video/Mde2q7GFCrw/video.html3m54s) Binary search is introduced as an optimization technique to find the minimum capacity needed.
- [16:49](czcams.com/video/Mde2q7GFCrw/video.html6m49s) The binary search approach eliminates capacities that are not possible and updates the answer with the lowest possible capacity.
- [18:25](czcams.com/video/Mde2q7GFCrw/video.html8m25s) The time complexity of the binary search solution is O(N * log(Sum - Max)), where N is the number of items and Sum and Max are the sum of weights and the maximum weight, respectively.
- [19:50](czcams.com/video/Mde2q7GFCrw/video.html9m50s) The C++ code for the binary search solution is demonstrated, and viewers are encouraged to find code for other programming languages in the video description.
concise and helpful explaination
you are artist too bro, multitalented striver
solved by myself, All thanks to you.
Understood and solved by myself
Thanks a lot Bhaiya. You make it easy peasy problem 😀
At 15:11 bhaiya you said high=23, but actually mid was=32 before, so new high=mid-1=32-1=31
hnn bhaii mee bhi yhi soch rhaa thaa tbbhi comment dhundh rha tha ki kisi nee to kia hogaa
nice explanation
Understood, thank you.
Nice explanation 👌
Another code for same approach:-
bool f(int mid, vector &weights, int d){
int day = 1, temp = mid;
for(int i=0;i
mast habibi
Living Legend!
NICE SUPER EXCELLENT MOTIVATED
Understood !! 😍😍
Nice explanation
Atlast got it❤❤❤
Superb sir ❤
Amazing question
Understood✅🔥🔥
solved it on my own, yay!
Well done
well well well now i am solving leetcode medium question without any help in the optimal way thank you striver!
Understood ❤
i was able to do it by myself...........thanks to striver;
return happy😆;
Understood 🎉
Understood!
understooood :)
Understood!!
going smoothly
Thank You
Understood !!!!!
Bro by when your whole dsa sheet will be covered, placement coming up?any eta approx?
Thank you Bhaiya
Understood
Possible function takes time to understand but clear now
bool isPossible(vector &weights, int d, int mid){
int dayCount = 1;
int sum = 0;
for(int i = 0; i < weights.size(); i++){
sum += weights[i];
if(sum d){
return false;
}
sum = weights[i];
}
}
return true;
}
understood!
if weights are 1 2 8 9 and d=2 will it give correct answer??
understood
what's the overall time complexity of binary search algorithm in this question
Because first loop to find summation and maximum element takes O(n) and then the binary search algo which takes (log2(sum-maxi)), after the algo we call the findDays function which take O(n) time complexity.
so, what's the time complexity of the code
Thanks You!!
It would be O(n*log(sum-max)), but if you want the exact time complexity taking into account the summation and maximum, then O(2n + n*log(sum-max)).
It was just an awesome video... but pls tell me... why int days is initialised with 1 .... why not int days=0;
bhaiya timestamp 15:06
here mid-1=high=point 31 ,not point 23.
same I was searching for this comment 😅
17:00 opposite polarity
I am thinking about taking the arr[i] + arr[n-i-1] elements together in the ship , then capacity would be 11? right?
hi @striver , when to use while(high - low >1) condition
I don't use it anywhere, all problems can be solved without that, if your base is clear
🔥🔥🔥🔥🔥🔥🔥🔥
❤❤❤
Undertsood
Done
I think in linear search return the capacity not daysRquired
Why the weights are not sorted then also it works, please let me know the function which is inside while loop
Isn't this same as painter partition problem?
❤
can anyone tell, while filling the boat why least weights possible are taken first??
17:59 ✅
"understood"
I have doubt in first example the answer must be 11 as you can take 1st and last element sum everytime so it will be 11
You need to take consecutive elements :)
Can anyone look up at my code and find mistake . I got wrong answer of this ques i.e capacity to ship packages within d days .
class Solution {
public:
int caldays(vector& weights, int cap){
int sum=0, cnt=0;
for(auto it: weights){
sum+=it;
if(sum
Low has to start from the maxElement in the array, other then that I see no error...
min days will be 1 not 0, just change days = 0 to days = 1 in the caldays function, also start low from the max element in the weights array
@@swapnil243 Correct
@@swapnil243 but it will. Without changing days in cladays
@striver please make full dsa paid or free course for competitive programming. I am watching your videos from past 5 months but still I am unable to solve new problems or codeforces ,codechef problems
Can u make paid live full course .
I am highly requested to u please launch your course from basic to advanced competitive course. programming course
join tle-eliminators
@@takeUforward please launch paid cp course we want to learn from you, you explain very well
Day 2 till here
hello bhaiya , as a tier 3 student should i focus more on DSA or web development. Learning web d. only that much to make 2 to 3 project is enough or should i go in depth in both dsa and web
I think the focus should be on DSA. Projects can be sorted out later, but DSA is something which will get you an interview call.
Web development projects will land you up in cheap companies. Strong DSA will land you up in Maang or good product companies. Choice is yours.
@@thelostguy1212 #FAANGM
bro i have passed out from cse branch from tier 3 without any job 3 star on codechef and good rating on leetcode and 500 problems solved but everyone else with other dev skills got a package except me rest u decide becoz at the end it's your call always but try to balance both dev+dsa
do web dev and master the skill to that level that each company wants you for your skill. dsa is not a thing to do its just problem solving kind of thing, never solve it for the numbers, just make sure whatever you do , u should be the best in it!! if you are in 1nd or 2nd year explore development field more
15:14 high should be 31 na?
yes but answer comes the same in this case
class Solution {
public:
bool func(vector& v , int cap ,int day){
int days=1 , load=0;
for(int i=0 ; i< v.size() ; i++){
if(load + v[i] > cap){
days++;
load = v[i];
}
else{
load += v[i];
}
if( days > day){
return true;
}
}
return false;
}
int shipWithinDays(vector& weights, int days) {
int low = INT_MIN , high = 0 ,ans=-1;
for(int i = 0; i < weights.size() ; i++){
low = max( low , weights[i]);
high += weights[i];
}
while( low
First comment
why we are initializing days with 1
This problem is same as BOOK ALLOCATION PROBLEM
Striver, please upload the solution of k closest elements.
It's Leetcode problem no. 658
It's a binary search question.
Why we have returned low here
@@kavyabanka4482 please dry run your code
@@kavyabanka4482
Bcoz it is based on polarity concept
It is a heap question
heap ka h dude
all the question are similar to previous one
UnderStood
this question can also be solved using previous video idea
#include
int possible(vector&weights,int posans,int days)
{
int n=weights.size();
int count=0,posday=1;
for(int i=0;iposans)
return false;
if(count+weights[i]>posans)
{
count=0;
posday++;
}
count+=weights[i];
}
if(posday
hehe solved by self
us