Largest Divisible Subset | Dynamic programming | Leetcode

This video explains a very important dynamic programming problem which is a variant of longest increasing subsequence (LIS).The problem is to find the largest divisible subset in such a way that all the elements in the subset are pairwise divisible.We need to return all the subset elements irrespective of their order.I have explained how to apply recursion and backtracking to this problem and i have also shown why recursion will fail.I have shown how this problem can be reduced to longest increasing subsequence problem (LIS).I have shown all the steps clearly with proper examples and at the end, i have shown the code walk through.CODE LINK is present below as usual.For the DAY-13 leetcode problem "Largest Divisible Subset", SORTING is essential and it cannot be solved without sorting because a number should have all the divisors to its left to be absolutely sure about including it in the same subset.This ASC order is important for decision making. Consider [9,18,6]. Here, if we are at 6 then we will compare with 18 and it will divide and so we will try to include in the SET with 18. But 18 is already in a SET with 9 which is [9,18] and therefore this will give wrong answer. If we first sort it to [6,9,18], then this will always give you correct answer.So, please ignore what i said about solving without sorting. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
SIMILAR PROBLEMs:-
Longest Increasing Subsequence (LIS): • Longest increasing sub...
Longest common subsequence (LCS): • Longest common subsequ...
Longest common substring: • Longest common substri...
Longest palindromic substring (LPS): • Longest palindromic su...

[@jamebozo]

by far the clearest explanation i've come across, thanks for explaining the thought process! you're awesome.

[@techdose4u]

Thanks :)

[@neerajpant4071]

what makes your different is you explain the thought process which includes the complexity stuff in detail. Absolutely brilliant

[@techdose4u]

Thanks :)

[@lampyclampy]

keep posting , this is the best way to teach DS and ALGO by solving problems .

[@techdose4u]

👍

[@ahmedkhaled8046]

Very good. You explained everything in a fast and simple way. The intuitive, the idea, the code... everything. Thank you and keep up the good work.

[@techdose4u]

Welcome :)

[@devendradahale546]

Great approach . When I saw this problem I wasn't able to come up with identifying some overlapping subproblems. You explained it very clearly as it is variation of lis and the transitivity property by which we do it by dp. Thank you keep doing great work and keep helping others ❤️

[@srinivasreddydanda1777]

Thanks for posting the June Leetcode Challenge problems. Your explanation is really helpful!!!

[@techdose4u]

Thanks :)

[@shalomalexander7811]

I saw many videos...but this video just made the whole dp[] table construction concept very clear. I Salute you!!!!. Teach me how you learnt to solve like this

[@techdose4u]

Thanks bro. Keep learning and practicing. You will master is soon :)

[@pendyalaabhishek8866]

you deserve a lot more subscribers . only thing is if people don't even know the basics and watch this video they wont like it .i am asking people to not forget liking this video .

[@techdose4u]

Thanks

[@shresthmishra9329]

Thank you TECH DOSE. As a beginner, i have learnt so many concepts from this channel.Thank you for existing. :3

[@techdose4u]

Keep learning :)

[@zaibaas20]

I feel fortunate enough to have found your channel:)
Thanks a lot !

[@techdose4u]

Keep learning :)

[@Subhasish8844]

I dp was a list of list..but the way you found the whole max list by just storing the length was awsome..Generally what I do is I solve the daily challenge and then I come back and see how you have done it...and I am surprised everytime..keep up the good work..

[@techdose4u]

😅 Thanks

[@abhijithumesh2974]

You are doing such a good job of posting these videos. Thanks a ton for such wonderful explanations!

[@techdose4u]

Welcome

[@jeremyhon2775]

Amazing explanation. I read the solution on LC but didn't really get it. this video is a lifesaver!

[@techdose4u]

Thanks :)

[@aakashyadav6228]

Awesome explanation. No doubt this needs to be the best solution video for this problem on the internet.

[@techdose4u]

Thanks :)

[@100bands]

Always on point. It works without the previous variable as well. You just need to decrement max whenever you find a match

[@techdose4u]

Let's say your array is (1,2,3,4). Now your DP table will be (1,2,2,3). Your max will be 3 and you start with last element 4. 4 will get included, max will be reduced to 2. Now 2 matched the 3rd element and so 3 will also get included which is wrong because we need to check if it divides the previous element and so we need to store the previous element somewhere. So how did you manage this?

[@100bands]

@@techdose4u Ah I see, you are right.. I guess the test case is incomplete because mine actually got accepted without checking the divisibility of previous element.

[@ShubhamMahawar_Dancer_Actor]

Initially ,i tried by myself but failed to get any approach then just saw your video and by the time you said LIS, i solved it ny myself and got accepted.
But how you have thought is it LIS variant problem,main your thinking ability damn good.

[@techdose4u]

I solved and then realized it's LIS 😅

[@ERROR-os9wm]

Best solution explained by any other video present in CZcams....thanks a lot

[@techdose4u]

Thanks :)

[@mehular0ra]

Even though I could solve the question, I find it really useful to see your videos

[@techdose4u]

😁

[@kunwar2010]

Small mistake from 8:35 the condition should be arr[i] % arr[j] == 0. But overall great content, please keep posting videos.

[@indianking0017]

thanks for posting made concept very clear no waste of time whole video is content learnt so much

[@techdose4u]

Welcome :)

[@rohitsai806]

I stored the ans in a vector every time the max is updated. But the way you found out the subset finally was awesome

[@techdose4u]

Thanks :)

[@lipishah474]

Sir you are awesome and the way you explain problem makes my day. I really appreciate your effort and time 👏👏

[@techdose4u]

Thanks :)

[@surajkiranreddymothe686]

Thanks for a Great Explanation. And Special Thanks for doing it in C++.

[@techdose4u]

Welcome :)

[@noctua7771]

Great explanation! Thank you very much

[@vishwajeetpawar3009]

Really nice explanation , I was confused about how this problem is related to LIS and you cleared my doubt😇😇😇 !!! thanks a lot , very very clear explanation !!!

[@techdose4u]

Thanks 😊

[@adityaojha2701]

Now whenever I search questions on youtube, I always hope u uploaded the ques.

[@techdose4u]

❤️

[@paragroy5359]

Nice explanation your videos are really good...please keep on making such videos...you are doing a great job.

[@akkzhol1]

Thank you very much for your effort! It was really helpful and clear!

[@techdose4u]

Welcome :)

[@prathamkesarkar]

Your solution works like a charm

[@techdose4u]

👍🏼

[@parvezmulla3324]

amazing! crisp and clear explanation.

[@techdose4u]

Thanks :)

[@mehular0ra]

I love your videos, really a good way to improve sills in DS algo

[@techdose4u]

👍

[@The_AK31]

16:53 the rap got me there

[@siddhartha.saif25]

thanks a lot! very nice explanation!

[@techdose4u]

Welcome :)

[@algorithmimplementer415]

wow ... finding it as a variant of LIS is just cool.

[@techdose4u]

😅

[@downtowngedi]

great explanation, thanks for sharing 👍

[@srikantsharma6430]

Very well explained!

[@haodongwu1313]

nicely explained. Thanks! 👍

[@techdose4u]

Welcome 😊

[@amartyadutta2477]

Thank you sir 👍 I daily watch your awesome video sir .♥️

[@techdose4u]

Welcome :)

[@akshatsinghbodh3067]

Thanks a ton!!🙌🙌🙌

[@vsreeniketan]

you are simply amazing...!!!!

[@techdose4u]

Thanks :)

[@yashgupta3127]

Urghhh i was so close to the solution.I am new to programming and have not touched dp yet but unknowingly i was on right track but was having problem with how to return the elements the part where you used prev idk why it didnt came to my mind.

[@techdose4u]

:) It's good to see that even without DP experience you were close.

[@GARIMAJAIN-ww6mc]

Awesome explanation🔥🔥

[@singurubhavana8368]

Excellent as always 🙌

[@techdose4u]

Thanks :)

[@hymnish_you]

Luckily you are a genius and gladly an awesome teacher.

[@akashyadav3211]

Good explanation 👍

[@legel93]

Hi, the explanation really helps, thanks!
At the end of your video the code suggests you do dp[i] = dp[j] + 1 isn't it supposed to be dp[i] ++? This when the conditions are met and you increment dp[i]
Thanks for any replies in advance!

[@techdose4u]

That might work because we are going from left to right and checking sequentially band the elements can only increase by one value maximum moving to the right.

[@legel93]

@@techdose4u many thanks! :)

[@divakarbhardwaj7322]

Is there any approach in recognising these dp problems? Like you recognised Longest Increasing Subsequence. Is there any method other than just trial and error to approach a problem like this?

[@techdose4u]

The difficult part in this problem was to recognise it's a LIS problem. I solved it then realized it's LIS 😅 There is no said rule of identification. You will just recognise it easily if you have practiced a lot.

[@divakarbhardwaj7322]

@@techdose4u alright. Practice is the only answer then.😅

[@sharabiani]

How can we find the answer (the subset) if we have taken the recursive/memoization approach (top-down) ?

[@techdose4u]

Follow LIS. It will have exactly same code.

[@rururi3262]

easy explanation!

[@competitiveprogrammingwith7752]

Nicely Expalained Keep it up

[@techdose4u]

Thanks

[@techykush7192]

thanks bhaiya amazing teaching style

[@techdose4u]

Thanks

[@canopus74]

Thanks, Sir Ji:)

[@techdose4u]

Welcome :)

[@ALOKRAWSINGHAM]

Hi, thanks for the clear explanation. Can you please explain the Rain Trapping Water II from leetcode?

[@techdose4u]

Later bro. Now I am busy with this.

[@ALOKRAWSINGHAM]

Actually I had faced that question recently in one of the company but I was not able to solve.

[@silajmunna2854]

Bro write the java code also ...btw your explanation is simply superb ♥️

[@techdose4u]

Thanks. Dunno java yet 😅

[@exodus5948]

@@techdose4u maybe all companies use java python , but cpp has separate fan base

[@100bands]

Java Code:
class Solution {
public List largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
List subsets = new ArrayList();
if(nums.length == 1){
subsets.add(nums[0]);
return subsets;
}
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int max = 0;
for(int i = 1; i < nums.length; i++){
for(int j = 0; j < i; j++){
if(nums[i] % nums[j] == 0 && 1 + dp[j] > dp[i]){
dp[i] = 1 + dp[j];
}
max = Math.max(max, dp[i]);
}
}
for(int k = dp.length-1; k >= 0; k--){
if(dp[k] == max){
subsets.add(nums[k]);
max--;
}
}
return subsets;
}
}

[@ShubhamMahawar_Dancer_Actor]

Can you provide pseudo code for ,if we don't SORT the array how it will done cz i am getting WA while this approach

[@techdose4u]

I have provided the answer in community post. We can't solve this without sorting.I have explained why. Please go through the post.

[@taxila4047]

The explanation is very clear .But why dp size is n+1.

[@abe10]

Good one, subbed!

[@techdose4u]

Thanks :)

[@ayushgarg5929]

How to get original subset...the subset you have found is sorter subset ??

[@AnilGupta-iv1rz]

Is it really needed to maintain previous element while constructing subset?

[@techdose4u]

I did it to see if the Max value matches then the current element should also divide the larger (prev) element. So I maintained it. People have also solved without prev.

[@priyanshuchaudhary1135]

best explanation

[@spetsnaz_2]

what about article writing...many of us want to contribute articles on your website....

[@techdose4u]

By tommorow probably I will upload the process.

[@abdullahzaidan7394]

O bhai maza aa gaya

[@techdose4u]

👍

[@jagritbhupal5836]

Thanks man.

[@techdose4u]

Welcome

[@victorcui4014]

Is there code for the brute force recursive solution?

[@techdose4u]

I don't have it with me. Try writing it. It will be simple. Very similar to LIS recursive code. You need to just add your division constraint to that.

[@victorcui4014]

@@techdose4u Thanks I wrote something like pastebin.com/E2vUjP0L in Python

[@hhcdghjjgsdrt235]

very smart,

[@starc701]

16:06 , i dont understood how (6,3,1) is a subset ? is it not a subsequence ?
I think the question statement is wrong , how can leetcode write subset , question should be find the largest subsequence.

[@SunilKumar0261]

excellent

[@techdose4u]

Thanks

[@ijaz2020]

6:40 I suppose it is AND operation.

[@techdose4u]

No it is OR operation. Please read the question again.

[@ijaz2020]

@@techdose4u Any two numbers you can take (a%b == 0 || b%a == 0) this condition will always be true. We will end up adding every element to the subset.

[@stankafan6688]

Thanks bhaiya 😊

[@techdose4u]

Welcome :)

[@MrDeepakekbote]

Hey buddy, could you please create video about z algorithm?

[@techdose4u]

Sure but it will take some time.

[@tanyakemkar310]

Thanks

[@utkarshverma5486]

OH MY GOD! I could never have linked it to LIS. Now I feel so stupid =.=``

[@techdose4u]

😅

[@shivannagarivenkatreddy7623]

Please provide the java code for all examples

[@TheTushar35]

You are always awesome!

[@techdose4u]

😅 Thanks bro

[@user-nw9fl1pe4p]

Which book can I learn DSA？

[@techdose4u]

Can't recommend you any DSA book since I din't follow anything.

[@sudhanshusingh211]

why the order is not important subset is part of the array by removing some element by maintaining order. How 1,2,4 is subset of 1,4,2,6,7

[@siddharthbora3961]

napa valle
class Solution {
public:
vector largestDivisibleSubset(vector& n)
{
sort(n.begin(),n.end());
vectorhawa(n.size(),1);
vectorhawa2(n.size());
hawa2.push_back({n[0]});
for(int i=0;i

[@sanketdedhia9981]

Java Code with the same logic:
class Solution {
public List largestDivisibleSubset(int[] nums) {
List result = new ArrayList();
int n = nums.length;
if(n == 0) return result;
Arrays.sort(nums);
int max = 1;
int[] dp = new int[n+1];
dp[0] = 1;
for(int i = 1; i=0; i--){
if(dp[i] == max && (prev%nums[i] == 0 || prev == -1)){
result.add(nums[i]);
max-=1;
prev = nums[i];
}
}
return result;
}
}

[@RahulKumar-de7rn]

Bro explain contest q4 q3

[@techdose4u]

Later bro. I am very with these daily problems.

[@abhinavranjan3599]

isn't the question wrong?
It should be subsequence and not subset.
A subset cannot have interleaving elements but a subsequence can.

[@vamshikrishna8143]

Can someone tell me how this is true?
answer[i] % answer[j] == 0, or
answer[j] % answer[i] == 0
since
1 % 2 = 1 and
2 % 1 = 0

[@rururi3262]

it's OR not AND, one condition is true

[@shivamjoshi6648]

without sorting the answer will be wrong

[@ahsanzkhan]

Clearest explanation! Appreciate what you’re doing.

[@techdose4u]

Thanks