BS-15. Capacity to Ship Packages within D Days

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

[@ArpanChakraborty-do6yz]

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😍😇😇

[@anonymousanonymous7507]

gawd

[@arujgarg7267]

dude exactly same, i was also able to solve this one and the last one on my own. this happened for the first time!!

[@luckygarg2294]

@@arujgarg7267 Exactly same... Solved this and previous 2 problems on my own

[@Satyendra_Prakash17]

solved it on my own , woohoo confidence is just sky rocketing !! thank you striver

[@siddharth892]

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

[@divingdabbler2035]

Ikr, right now the question seems more like binary search over series of knapsacks instead of contiguous sums

[@harshvardhansankpal716]

yup, i was literally thinking the same thing, i thought if i only take consecutive days i might get error in leetcode.

[@sauravchandra10]

The way you explain and write the code so clearly is what is so unique about you. Clearly understood, thanks!

[@grannymuffins8882]

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

[@elizabethr5161]

Crystal clear explanation striver... Clearly understood everything...Thanks a lot for this awesome series.

[@samreenimam8608]

SALUTE HAI BHAI..!! kya smjhaya hai ..itna easy logic!!... blown away! Thank you rahega

[@adityarajvermaa]

man..even this one i coded down myself...understanding the previous ones...thanks bhai

[@rushithagudipudi7742]

❤understood, next level lecture , this is what the tier 3 students wish to listen in classroom

[@tanishkumar5827]

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

[@cinime]

Understood! Super excellent explanation as always, thank you very much for your effort!!

[@lucario404]

aapki videos shuru majboori mei kiye the, lekin ab maza aane laga hai :)

[@Qasim78669]

sammmmee😂

[@vishious14]

Was able to solve this on my own. This question is similar to minimum days to make m bouquets. Thanks a tonne, Striver !!!!

[@ishangujarathi10]

superb explanation, 80% coded it myself, tysmm

[@abhaypandey2668]

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

[@kanishkkala16]

Can u share where were doing this problem, was it a platform other than leetcode ? Kindly share

[@Isagi__000]

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.

[@DEVILGAMING-to6bn]

sorry to say but studying DSA with you and LOVE sir combined is just better than best

[@ajaynaik2480]

love babbar?

[@DEVILGAMING-to6bn]

@@ajaynaik2480 yaaa

[@TUB_HUB]

Where are you placed now??

[@SumitSingh-dc8pm]

*Completed now, thanks for such lovely content.*

[@ayushagarwal5271]

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..

[@sayandey2492]

Wow...the portrait of the ship is so good 😃

[@teeyaojha4365]

mistake at 15:03 it will come to 31 not 23, but its ok. under stood.

[@satyamraj2779]

agree

[@user-ti3bd8mp1w]

Understood Thank You striver for such an amazing explanation

[@Codro09]

I was able to code in less than 7 mins (thala for a reason....naah, obv u the reason).....thanks a lot.

[@manavsingh5919]

Thank You Striver understood everything🙂

[@MYMIND252]

- [00:17](kzbin.info/www/bejne/g5XIY6RtfKt2qNk) The problem is about finding the minimum capacity needed to ship packages within a given number of days. - [01:49](kzbin.info/www/bejne/g5XIY6RtfKt2qNkm49s) An example is given where if the ship's capacity is 100, all packages can be shipped in one day. - [03:22](kzbin.info/www/bejne/g5XIY6RtfKt2qNkm22s) It is demonstrated that a capacity of 10 leads to shipping taking more than the given number of days. - [04:20](kzbin.info/www/bejne/g5XIY6RtfKt2qNkm20s) Increasing the capacity to 15 allows shipping all packages within the given days. - [06:11](kzbin.info/www/bejne/g5XIY6RtfKt2qNkm11s) The answer must be between the maximum weight of a product and the sum of all weights. - [08:01](kzbin.info/www/bejne/g5XIY6RtfKt2qNkm1s) A function is described to find the number of days required to ship with a given capacity. - [12:32](kzbin.info/www/bejne/g5XIY6RtfKt2qNk2m32s) The initial solution has a time complexity of O(N^2) due to linear search. - [13:54](kzbin.info/www/bejne/g5XIY6RtfKt2qNk3m54s) Binary search is introduced as an optimization technique to find the minimum capacity needed. - [16:49](kzbin.info/www/bejne/g5XIY6RtfKt2qNk6m49s) The binary search approach eliminates capacities that are not possible and updates the answer with the lowest possible capacity. - [18:25](kzbin.info/www/bejne/g5XIY6RtfKt2qNk8m25s) 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](kzbin.info/www/bejne/g5XIY6RtfKt2qNk9m50s) 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.

[@AnmolGupta-oj4lm]

Understood Very Well!

[@IAmIndraTheGod]

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

[@chinmaygambhirrao9774]

Man, you're legend🤓. Thanks

[@TON-108]

Understood! Thanks :)

[@92AkshaySharma]

concise and helpful explaination

[@K_EN_VisheshSaini]

Another code for same approach:- bool f(int mid, vector &weights, int d){ int day = 1, temp = mid; for(int i=0;i

[@prabhatece0488]

At 15:11 bhaiya you said high=23, but actually mid was=32 before, so new high=mid-1=32-1=31

[@kanhiyasharma3648]

hnn bhaii mee bhi yhi soch rhaa thaa tbbhi comment dhundh rha tha ki kisi nee to kia hogaa

[@user-or5oz1pk2x]

Thanks a lot Bhaiya. You make it easy peasy problem 😀

[@user-js1rx8rs9p]

you are artist too bro, multitalented striver

[@sujalgupta6100]

solved by myself, All thanks to you.

[@NazeerBashaShaik]

Understood, thank you.

[@saswatrath4646]

Understood and solved by myself

[@gouravbhatt479]

i was able to do it by myself...........thanks to striver; return happy😆;

[@U2011-n7w]

nice explanation

[@user-is6ky7pp2n]

Understood !! 😍😍

[@md.imrankhan6912]

Living Legend!

[@aliakbaransaria3-925]

Nice explanation 👌

[@CodeMode9313]

mast habibi

[@MJBZG]

solved it on my own, yay!

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@dhruv2014]

Nice explanation

[@rushidesai2836]

Amazing question

[@diptamoymitra7486]

Atlast got it❤❤❤

[@CrazyHunk14]

well well well now i am solving leetcode medium question without any help in the optimal way thank you striver!

[@utsavseth6573]

Well done

[@thenriquevicentini]

Understood!

[@kiranmoura2974]

Superb sir ❤

[@YourCodeVerse]

Understood✅🔥🔥

[@srinathv1412]

Understood !!!!!

[@GuruPrasadShukla]

going smoothly

[@senseiAree]

Understood ❤

[@her_soulmate]

Understood 🎉

[@ambaradhikari7425]

Bro by when your whole dsa sheet will be covered, placement coming up?any eta approx?

[@vipu18]

Understood

[@gunjjoshi5687]

Thank You

[@pihus3498]

understooood :)

[@joeljacob4685]

Understood!!

[@user-tk2vg5jt3l]

Thank you Bhaiya

[@humanity7880]

understood!

[@Manishgupta200]

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; }

[@shyamkumar712]

if weights are 1 2 8 9 and d=2 will it give correct answer??

[@kushagramishra5638]

understood

[@user-dq4gq2sd5j]

It was just an awesome video... but pls tell me... why int days is initialised with 1 .... why not int days=0;

[@cyanideyt9579]

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!!

[@manavpatnaik222]

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)).

[@amittiwari360]

Why the weights are not sorted then also it works, please let me know the function which is inside while loop

[@sattwikmanna7851]

bhaiya timestamp 15:06 here mid-1=high=point 31 ,not point 23.

[@SomethingBetter570]

same I was searching for this comment 😅

[@VinayQ-]

I think in linear search return the capacity not daysRquired

[@saqlainkadiri]

Isn't this same as painter partition problem?

[@yugal8627]

hi @striver , when to use while(high - low >1) condition

[@takeUforward]

I don't use it anywhere, all problems can be solved without that, if your base is clear

[@VishalGupta-xw2rp]

17:00 opposite polarity

[@Omneeshkushwah9695]

@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

[@takeUforward]

join tle-eliminators

[@iWontFakeIt]

@@takeUforward please launch paid cp course we want to learn from you, you explain very well

[@girikgarg8]

Done

[@user-vs4ng8ul9x]

can anyone tell, while filling the boat why least weights possible are taken first??

[@codeman3828]

Undertsood

[@shreshtasingh2384]

🔥🔥🔥🔥🔥🔥🔥🔥

[@rohit.mnnita]

17:59 ✅

[@piyushgarg41]

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

[@sayakghosh5104]

Low has to start from the maxElement in the array, other then that I see no error...

[@swapnil243]

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

[@ayushmukhopadhyay7470]

@@swapnil243 Correct

[@piyushgarg41]

@@swapnil243 but it will. Without changing days in cladays

[@draxxgamingf.f6369]

🎉🎉🎉

[@BiswajitDas-fj5gp]

❤❤❤

[@globalcuber9816]

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

[@takeUforward]

You need to take consecutive elements :)

[@drizzle01]

❤

[@mustafa-zl9ox]

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

[@raghavkansal3765]

"understood"

[@poornima8206]

why we are initializing days with 1

[@bingereviewer7752]

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

[@sauravchandra10]

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.

[@thelostguy1212]

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.

[@MohanC-tv5kk]

@@thelostguy1212 #FAANGM

[@mukulkhanna26]

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

[@davendrabedwal830]

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

[@footybanter1]

Day 2 till here

[@ritikverma3206]

First comment

[@RahulKumar-nd2sp]

15:14 high should be 31 na?

[@pratikshadhole6694]

yes but answer comes the same in this case

[@siddhantgureja7803]

Striver, please upload the solution of k closest elements. It's Leetcode problem no. 658 It's a binary search question.

[@kavyabanka4482]

Why we have returned low here

[@user-iq8pu4xq9o]

@@kavyabanka4482 please dry run your code

[@vuthunoorigeetha8393]

​@@kavyabanka4482 Bcoz it is based on polarity concept

[@vuthunoorigeetha8393]

It is a heap question

[@khitijkarmakar]

heap ka h dude

[@pravalikavemula6952]

This problem is same as BOOK ALLOCATION PROBLEM

[@user-td9uu2om9f]

all the question are similar to previous one

[@rahulhembram4519]

UnderStood

[@ishangupta803]

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

[@cenacr007]

us

[@kshitijmishra2716]

hehe solved by self