Text Justification Dynamic Programming

Given a sequence of words, and a limit on the number of characters that can be put in one line (line width). Put line breaks in the given sequence such that the lines are printed neatly
github.com/mission-peace/inte...
github.com/mission-peace/inte...

[@RicardoBuquet]

Dont really understand the explanation from minute 7:20 onwards. :(

[@becharam1]

I was traversing so many places to learn dynamic program but at last these video lectures made my job easy and understandable...awesome, thanks a lot

[@robinganpat250]

Hey, Filling the first 2D array which contains the values of the squared left-over length of a line is N^2. This is for large texts with like 30.000 words a problem. Wouldn't it be possible to save it in N*L? If so, how?

[@Iwebguru]

How the hell would anyone think of this in an interview?

[@PrathamMantri]

Thats what I was thinking while watching the video, then decided to go with greedy algorithm :P

[@08himanshu]

It has a simple solution also. You can solve it like matrix chain multiplication. Problem - 3

[@sahibjotsinghbedi292]

@@PrathamMantri I did the same

[@CodeCampaign]

You can solve this problem in more simple manner, like we do all other partitioning problems. Check the problem on word partitioning and then try to apply the same logic here. This solution is over complicated.

[@kipa_chu]

thats why not everyone is a google, apple engineer

[@srktheking1]

awesome job tushar!! have to say yours is the best tool for learning dynammic programming I have across simple and efficient at the same time! keep up the good work man! you are helping out so many people like me, thanks for that!

[@sejalmandhan5635]

Can you tell me how he store 5 in result array?

[@WeeZy1534]

I LOVE YOU !

[@justapolitecommenter351]

You rock man. You rock !

[@amanpreetsinghbawa1600]

Tushar sir your programming videos have helped me a lot. Just one point to mention is that please give the recursive relation so that we can get completely connected with the solution. Thanks!

[@vorasagar7]

agree

[@diptiprakashsinha]

Agreed

[@shubham_chime]

+Tushar, Thanks a lot for this video. I understood the solution but I did not get how you came up with thought of using dynamic programming in first place. What was your thought process ?

[@TechCluesByAbsek]

This is the only satisfactory video in KZbin till now thanks a lot for that

[@varuntaneja7073]

I wasn't able to wrap this solution around my head . Thanks for the explanation!

[@sejalmandhan5635]

Can you tell me how he store 5 in result array?

[@maxwellward7533]

I didn't fully understand at first, but after re-watching and writing out the algorithm along with the video, it all makes sense now!

[@joeystechpluscode]

Hey Maxwell, This problem has been explained clearly in my channel and students are really complementing the explanation. Just check it out kzbin.info/www/bejne/eX6vpJ2rZq6DhKs

[@ashishmadaan9488]

very great explanation of the question. Thank you a lot.

[@user-vm5pz5gz9c]

Thank you, Tushar! This is awesome

[@MOHDSALMAN-sj2zu]

U explained it in very good manner. Thanks a lot.

[@deepsaxena2768]

Please try to give logical reasoning for taking any decision, like you started from left or can we club both the matrix into one but sol will become O n4 like that, will be really helpful

[@anandgupta8529]

Acc to Tushar-->Dynamic programing ==filling the table. No intutuion ,no logic, just fill the table

[@swethav5122]

Thank you so much, Tushar. Your videos are really helpful. I understood the procedure you have explained in this video. Can you tell me where exactly you have an explanation for the code for the Text Justification Dynamic Programming Problem?

[@sandeepsr5300]

Thanks a lot. As an extension of this i have one question. Given width and number of rows, how many times you can fit in that sentence? Next sentence can start after a space from last word. It will be helpful if you share the technique. Once again thank you.

[@sandipbeed]

at 7:56 .. can anyone please explain why 5 is assinged at last index in second array ??starting from 4 till 5 .. i dont get it where is 5th index

[@depinderpreetsingh3554]

+Sandip M. Waghmare : Actually it just means that if there is 5th indexed word then it would be in next line. You can easily understand it's concept by looking at other indexes as shown in the video. Hope that helps a bit.

[@dragnet232]

Great work, thx for your help.

[@JamesBond-jp2ep]

Hello, thanks for the nice video. I have the task to output a .txt file in c++ compiler with a justified width of 25 inputted by the user. I have to use ofstream and ifstream to read character by character and output each line so that the maximum number of character in a line is not more than 25. (not more than 25 characters) I need to solve this task urgently... :-( Could you please help me out?

[@tavvayaswanth]

Thank you Tushar, your videos are really helpful :)

[@madhuramjajoo8967]

Tushar Sir there is a O(nlogn) method for longest increasing susequence . Can this question be done in O(nlogn) also?

[@rogerbosman2126]

Thanks for the explanation, but when looking at the code I don't get it. In the video, you start doing the "where to break" analysis once you hit infinity between i and j. However, in the code, you just 'continue;'. How does this work? Where does this analysis take place in the code? Thanks!

[@ararbi90]

Can you please write the actual recursion!!!

[@angadrajsingh4311]

Amazing explanation for this question on youtube so far. Thankyou..

[@depinderpreetsingh3554]

Thanks for such a nice video :)

[@s1337m]

why do you square the number of white spaces?

So that the big individual spaces get more value than several smaller spaces. The same is done in TeX (en.wikipedia.org/wiki/Line_wrap_and_word_wrap#Minimum_raggedness).

[@ahmxtb]

Yes, TeX actually uses (width - used)^3. The ^3 is to amplify discouraging unused spaces.

[@cvryn7]

This was little complicated!!! but finally understood :P Thanks!

[@geniusmridul007]

In you video you missed out the traversal from 2 to 3 (excluding 3). I get that we have used the word at index 2 but is there a way to fix that such that we don't get this kind of repetition?

[@dk109k2dask9]

Great video Tushar!

[@nileshagrawal9520]

Excellent Explanation of the most of the problems. Helped a lot in understanding dynamic programming. Can you recommend any good book for reading and subtle explanation of dynamic programming problems

[@RiRiDingetjes]

You could do it in O(nm) where m is the max length of one line. Make a matrix sized [n][m/2]. Now every [i][j] stands for the words i-j to i.

[@SachinSharma-vd5fr]

Thank you Tushar, nice explanation... :)

[@rajeshkumarjha007raj]

Yes, we'll use Dynamic Programming.

[@AbhijeetAelkatwad]

:D :D

[@yingyinghu4906]

lamo

[@sudhirghandikota3360]

Thanks tushar...good job!!!

[@asifbilla4924]

Nice explanation.

[@mo3osman]

at 11:05 it should be 49 + 9 (best you can do from j = 2 till end), or am I missing something?

[@sejalmandhan5635]

Can you tell me how he store 5 in result array?

[@ektabhalwara9542]

ohk tushar , i found box stacking problem too. thanks ur vedios help a ton.and u look good in specs

[@alia2122]

Tushar, how would we solve if we got question saying, do not consider last row penalisation, that is wheneve is in last row at as long as it fits size lets sayy 10, it wont get penalised.

[@widmanm]

how do we implement this?

[@prashantsahu2959]

Why are we using sum of squares(spaces) for cost determination?

[@kevinnicaise4379]

Thank you ! :)

[@deepsaxena2768]

How the recursion tree looks like?

[@betamoo]

I think we can get the solution using 1d arrays instead of 2d array. The 1d array F[i] will still represent the cost of fitting all prev words including i We will use another 1D array Acc[i] to store the accumulated sum of word lengths up till i Acc[i] = sum(F[i] ... F[0]) which will help get the sum of any interval in constant time. Now the recursive formula will be F[i]= minimum of previous F[j-1] + the error introduced of putting words j..i in a new line F[i] = min( F[j-1] + (width - (Acc[i]-Acc[j-1]) + (i-j))^2) for j= i to 0 or until (Acc[i]-Acc[j-1]) + (i-j))^2 becomes larger then width

[@davidoh6342]

I see many people explaining this question with minimizing badness. But how is it any better than just iterating through the list of words, and reinitializing the every time I find the last word based on word length count and separating sentences?

[@arjunkhanna1803]

3:30 how can you tell that arrangement 2 is better then 1 only because the sqaure of empty spaces is greate? and why we should count the square, because after all number of empty spaces matter not square

[@joeystechpluscode]

This problem has been explained clearly in my channel and students are really complementing the explanation. Just check it out kzbin.info/www/bejne/eX6vpJ2rZq6DhKs

[@AbhijeetSachdev]

Thanks a ton Tushar :)))))

[@MaheshGaonkar22]

How J2 = 49 + 34 ? why not J2 = 49 + 9 ? I didn't get at 10:57 .. can anyone explain it?

[@KirubaEbenezer]

Thanks Bro.

[@HAAH999]

Super work, but you could have used the same cost matrix since its simpler. You set infinity immediately while you could have chosen to check the minimum of infinity and all other possibilities. T[i][j] = min ( "infinity" if total length > width otherwise "computed cost", min(T[i][k]+T[k+1][j])) I tried it and got the same result. We can set the start of new lines by just adding the index in the matrix as you did in previous videos to find the arrangement.

[@yernartalgatuly4252]

In 11:09. Why did you write 49+34? The best of 2 to the end of line is 9. Or I didn't understand

[@deltechdiaries5907]

how will we solve covid crisis? Roy : Yes, we will use dynamic programming for this

[@user-no5oi3eh8v]

Спасибо за видео

[@dawnoin]

It would help if you could also prove correctness of the algorithm. And, why should one choose a particular algorithm over another, inorder to solve a given problem.

[@CyberMew]

What is that 5x5 matrix about? What’s the value of x and y axis? I don’t get it, it’s not explained.

[@vrn11]

Why square? What is the justification?

[@tttuberc]

How is this method called "dynamic programming"? thanks

[@joeystechpluscode]

It starts from the lowest subproblem and moves to the highest problem, that's why. This problem has been explained beautifully in my channel and students are really complementing the explanation. Just check it out kzbin.info/www/bejne/eX6vpJ2rZq6DhKs

[@ektabhalwara9542]

Hey Tushar please upload vedio for Box Stacking problem too. please

[@syedabdullahzobair4490]

kindly Explain RNA secondary Structure as well please !!

[@kumarshubhamshivhare]

Good job

[@komalanand3507]

can you please share git repo link again

[@shashankbajpai5659]

but what if one line can store more than 2 words?

[@nileshmare9662]

You have given a very efficient solution :bestofluck

[@bashaieralyousefi4038]

that is a great video , helped me a lot ! thank u

[@Official-tk3nc]

ola hu uber

[@ShivangiSingh-wc3gk]

Ugh I dont even feel like wrapping my head around this.

[@elissneia6027]

could anyone explain why 0-3 is INF? 0 Tushar 3 to 6+3+1 = 10 isn't supposed it be 0 ?

[@shriram5444]

For those trying to use recurrence relation mentioned at the end to solve the problem, m[n] or m[len] or m[5](in this particular example) is 0

[@The_Promised_Neverland...]

Here I come again after 9 months for this same question, History connects us lol

[@Lassar25]

For 4 to 4 the penalty should be zero, because it's the last line. If you don't believe me check out wikipedia on line wrap, and word wrap.

[@hulk94smash]

couldn't understand it clearly :(

[@Ankitbomb1]

NO explanation at all on why we are doing what we are doing. Really disappointed.

[@user-vr9ok5uw1x]

True, It is diappointing but it is one of the best explanation we have so far. Tushar, It would be much better if transition between the statements would be smoother. It saves a lot time on preparation as you cannot remember everything but the basic concepts.

[@augiegardner76]

You have some great videos but this one didn't do a great job of explaining the reason behind the solution as much as it explained the methodology behind arriving at said solution. The matrix and the two arrays could have been better elaborated upon

[@kvsrkrishnan]

kzbin.info/www/bejne/e3_coKttoLN-m7s

[@deathbombs]

I don't like how you jumped right into approaches before explaining the problem fully, like what's a space? (We learn afterward that it's whatever is left over by words)

[@vishalmishra9549]

salute

[@DarkLordAli95]

6:21 "10 - 2 is 4" you heard it here boys.

[@hemantsethi8467]

Stop nitpicking. Making videos ain't a piece of cake. It was 10 - 8 = 2 extra spaces. Cost = 2^2 = 4.

[@nileshmare9662]

Sir, your code for this question is wrong..try using following case. "aaa","12345","1234567","1234","123","1234", "1", "12345","12345678","12345". take width as 12.

[@mohammadkarami8984]

Thanks for the note. but it was not clear

[@joeystechpluscode]

Hi, no worries - this problem has been explained clearly in my channel and students are really complementing the explanation. Just check it out kzbin.info/www/bejne/eX6vpJ2rZq6DhKs

[@AbhijeetNayak-connect]

No body should be asking these types of questions during a Interview and expect this answer. You won't be able to judge a person by this question.

[@karthikkottugumada8930]

For anyone interested in why Tushar went for square: kzbin.info/www/bejne/e3_coKttoLN-m7s

[@lakhveerkaur2886]

At 6:17, Am I the only one who laughed when he corrected himself, and be like 10 - 2 is 4...oops no 10 - 2 is 2 and 2 squared is 4. watching at 1.5x makes it more funny! ;)

[@adhishmalviya2408]

hahaha...I was going to write a similar comment

[@markgraham2312]

Here's the coded solution: long solveBalancedLineBreaks(std::vector words, int limit) { std::vector cost(words.size(), std::vector(words.size(), std::numeric_limits::max())); for (size_t i = 0; i < words.size(); i++) { int sum = 0; for (size_t j = i; j < words.size(); j++) { // calculate: sum{i, j} |word]i]| sum += words[j].size(); if (j != i && sum limit) break; else { int value = (limit - sum); cost[i][j] = value * value; } } } std::vector mincost(words.size(), std::numeric_limits::max()); int i = words.size() - 1, j; while (i >= 0) { j = words.size() - 1; while (j >= i) { if (cost[i][j] < std::numeric_limits::max()) { int subcost = cost[i][j]; if (j + 1

[@johannstraburg194]

Pet peeve: Wrong pronunciation of "infinite".

[@anandchowdhury9262]

For people starting out in DP, please dont follow tushar's tutorials. His videos jumps straight into a well known solution. HIS VIDEOS DONT TEACH YOU HOW TO THINK. For dp it is very imp to come up with a recurance relation and identity the optimal substructure and overlapping subproblems. That is the base of your solution. Once you reach that, you can convert your soln to a top up approach. Watch the MIT lectures instead.

[@markgraham2312]

Your explanation of the dp is terrible. Very poorly explained. Your explanation of how to calculate the 2d array is clear, but I have no idea what you are doing to calculate the 2 1d arrays. Okay, I understand. The results array is the index of the last word + 1!

[@rohitjoshi6335]

lame

[@harshitsaluja3493]

Not at all helpful you are just telling how to solve not telling why we go ahead with Dp with this solution

[@gilbertwiosna7434]

his language is poor and sad

[@geniusmridul007]

In you video you missed out the traversal from 2 to 3 (excluding 3). I get that we have used the word at index 2 but is there a way to fix that such that we don't get this kind of repetition?

[@XAngelsLifeX]

Спасибо за видео