note : you may not be able to do this using memoization since all values of lookup table are not filled in memoization , so do this using tabulation since tabulation guarantees that all values of dp table are filled
Here you go recursion with memoization code ---> class Solution{ public: int minDiff(int arr[], int n, int lsum, int rsum, vector & dp){ if(n==0) return abs(lsum - rsum); if(dp[n][lsum]!=-1) return dp[n][lsum]; return dp[n][lsum] = min(minDiff(arr, n-1, lsum-arr[n-1], rsum+arr[n-1],dp), minDiff(arr, n-1, lsum, rsum, dp)); } int minDifference(int arr[], int n) { // Your code goes here int sum = 0; for(int i=0; i
Thank you very much, Sir, this Q was asked in my Microsft Interview and I was successfully able to clear it .. because I had watched this video once. Thank you again and you're videos are very helpful and awesome.
Their are 2 types of Teachers : 1. Who Write code and then explain you 2. Who explain you and then write the code.... The difference is 1st one indirectly wants you to remember the code and 2nd wants you to Develop logic because if u know the logic u can write the code on your own that makes you an independent Guy. Aditya Verma is the 2nd one !! :)))) Nice work...Nice Way of teaching !!
@@Harish-fx2mo Haha! Similar thing happened with me -- I used "He" (H capital) somewhere in the middle of a sentence and I was rudely reminded that "He" was reserved only for God! :-)
Seriously I have seen lot of other programming channels on TH-cam.. No one taught the way you did.. Connecting everything..No one can even reach ur level.. Best channel i would say.. Keep uploading.. Waiting for ur recursion and backtracking series.
Thanks brother, Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
Used in LC 1049. Last Stone Weight II Note to myself: You can start looping over last row dp matrix from range/2 to 0 and choose the first TRUE and BREAK, as first closest sum from the center would be the required sum.
@@insaneclutchesyt948or do half sum and run on sum/2 , the max value of last index at dp will be the max value possible but less than (if odd) or equal (if even) to the sum/2 , and get the last dp value , do absolute of sum-dpval*2
Actually i am confuse in the subset function, we should make all dp table as true or false, and what we need to return, can you please help me.? public static boolean subset_sum(int[] arr, int sum, int size) { // Table initilization boolean t[][]= new boolean[size+1][sum+1]; for(int i=0;i
We can actually reduce the space complexity by half... One observation is: Since only half of the last line is what we need, we can omit the right half of the matrix. i.e. we can create matrix of size something like.. t[ n+1 ][ ceil(sum/2) ]. And yes I have checked this approach, it works fine. In this you just need to check the last true in the last row of t matrix. and then desired output is total_sum - 2*(col_num_of_last_true). In this way, we can further reduce complexity( both time and space ) by not creating unnecessary vectors. I know ADITYA SIR knows this, he just told you in a way, which a newbie can also understand :)
I really appreciate your work and like your way of explaining this approach. I will just be commenting another approach of doing it using memoization. Intuition: 1. sum -> sum of all integers in the array 2. partitonOneSum -> the maximum possible sum which is less than or equal to (
Hands down these are the best tutorials for Data Structures and Algorithms out here! This guy helps build up the intuition and concepts like no one else.
Please take note that this strategy only works for an array of elements that are positive. Great job @Aditya, this playlist is very helpful & easy to understand.
When you realize your teacher is teaching the concepts so good that you come up with the approach in 10 mins without seeing the video . I still don't know how i figured out that let's take the sum of the whole array than divide it by 2, and find out the maximum subset sum in the array which is less than or equal to (total_sum/2) and thn take the absolute of total_sum and max_subsetsum. Thankyou so much @Aditya sir for this greate playlist . You are truely a DP god.
Wow! Great explanation. I am glad that you are explaining how you are developing DP solution rather than filling a table with some formula that most other TH-camrs do when they solve DP problems. After watching those videos I was clueless and frustrated about how the formula shown in those videos was derived. I am glad that I watched your DP Introduction video. After watching 0/1 Knapsack video, I subscribed to your channel because your content is AWESOME! I am pretty sure you will get many subscribers soon. Thank you for taking the time and effort in developing these videos.
I am really glad you noticed the difference between me and other youtubers who just teach for the sake of making videos. Please share and help this channel grow brother !! BTW one question, how did you land on my DP Intro video?
@@TheAdityaVerma For learning DP I watched MIT 6.006 Introduction to Algorithms DP videos (more theoretical but good), Abudul Bari's Algorithm videos (he is pretty good for basics and other algorithms but for DP he also started with filling table) then I tried to solve DP problems on LeetCode and I got stuck so I searched for interview related DP problems and then landed on Tushar Roy DP (garbage explanation), Jenny (table filling only), Back To Back SWE (he explains well but did not link Knapsack variations, not many problems), a few chinese TH-camr videos (difficult to understand as even they were speaking English they were not explaining well) and few other videos and recently 2-3 weeks ago I had seen your channel on TH-cam search for DP videos, I clicked on a random DP video in your DP playlist and did not understand what is going on. Then I was reading comments on Tushar Roy's DP video and there someone shared your DP playlist and said start from the beginning and you wont be disappointed, so I watched your DP Introduction video, then 0/1 Knapsack video and then I realized that your DP videos are the BEST on TH-cam!
You don't know but you may have revolutionized the way computer programming has always been taught. Your youtube channel is a slap on 99.9% computer programming professors in India.
after you get the vector, then the maximum of that vector will always be the answer as in (Range - 2*s1), everything is constant except s1, so to minimize it, we need to choose the largest s1 value.
@@ansumanmishra1757 but we want to return only the minimum difference between subsets, so how does it matter if there are repeated numbers in the array?
@@shadowofthecorpse9481 yeah , you are right . My bad. I did a pretty similar problem on codechef where we had to print the total number of such minimum difference. So i messed up . Thanks :)
summing up what we did is the best part of these tutorials which a lot of youtubers and even paid course's teachers miss out on. Seeing 40+ min video tutorials can make anyone forget small details but summing up what we did after each new step is the best thing that you have done.
Another approach that one can observe from this is, to minimize range - 2*S1 we need to maximize S1. Also, S1 is less than range/2 so we can just use the Knapsack directly with weight array as given array and value array also as given array but the capacity of the knapsack as range/2. This finds the maximum subset-sum below range/2. Thus, we can just return range - 2*S1 directly. This reduces the space complexity by half.
Very nice way of explaining.. thanks a lot for making this series. Its very helpful for people like me who are preparing for intern interviews. Please make a similar series on graphs and heaps also.. And please try to make videos shorter (around 15 mins)
WOAHHHHHHHHHHH I was able to solve the question just seeing the video till 6:04 Brute Force: Make all subsequence but that will result in time complexity of exponential In brute force, once you have made all the subsequence you just need to accumulate that particular subsequence and take a remainder as the total sum-sum of accumulated subsequence. After that make a variable ans = INT_MAX and put the minimum of total-remaining. Optimized: Try thinking of subset-sum where we take sum as the total sum of all the numbers in the array. Time Complexity = O(n*total) where total = sum of all the elements in the array. C++ Code : int minDifference(int arr[], int n) { int total = accumulate(arr, arr+n, 0LL),ans = INT_MAX, dp[n+1][total+1],remaining; memset(dp,0,sizeof(dp)); for(int i=0;i
At 40:23 do we need to iterate throughout the vector? Just substracting it twice of last element of the vector can give the minimum, as created vector will hold the maximum value at the last index and to minimize, we should substract maximum from the range
I started reading the comments before watching this video and it got me intimidated at first but the way you explain is so smooth, that I reach to solution before you show on the lecture. Kudos to the work you have done.
words cant describe how much happy i am that i came across your channel !you are really doing a great job ! your methods of approaching the problem are so good .you are actually teaching how to approach the problem and that is what sets you apart from the rest of the channels on TH-cam !thank you so much !saw your profile on linked in and directly sent you a connection request would be really happy if you accept it !!! thank you again !
I approached this problem like a 0-1 knapsack problem, except that value array and weight array both are same and you have to maximize value while keeping the weight below total/2. Made it much easier to understand.
While using the bottom up approach(Tabulation) isn't it enough to construct the boolean table until (sum/2 ) instead of constructing the table until (sum)? In the end all we care about is the value closest to (sum/2) right?
Taking minimum can be visualised in a number line as the distance between 2 points ie, S1 and S2 should be minimum. Which makes the s1 that is closer to center minimum.
Bhaiya bohot ache see samjh aa gya DP ... Aaj tak aisa ache see kissine nhi samjhaya... thanks a lot for ♥️ please upload regular Bhai..appko bohot support karenge...log paise leke bhi itna acha nahi sikhate thanks again @aditya Bhai 💝
Hi Aditya, nice lecture series. Its the first DP series i have started watching and with every upload i m still interested in watching. great work Also quick question, could you mention what would be the changes in case of negative values present in the array for minimum subset sum difference. thx!
This might help you guys. CODE:-(NO need to take a vector for all possible sum just take the last value.) vector dp(n + 1 , vector(sum / 2 + 1 , false)); for (int i = 0 ; i < n + 1 ; i++) { dp[i][0] = true; } for (int i = 1 ; i < n + 1 ; i++) { for (int j = 1 ; j < sum / 2 + 1; j++) { if (arr[i - 1]
@@mohdfaisalquraishi8675 for last loop we can reduce time complexity , because we know that its always first element coming from right side(from totalsum/2) which is true, that will be our answer, here is the most optimized code. No need even vector/list , no need to traverse dp from front to tsum/2, we can traverse in reverse direction, get first true element in dp, and get min sum using return (tsum-2*j) public int minDifference(int nums[], int n) { // tsum means = total sum int tsum = 0; for(int i=0;i
Thank you Aditya bhai.......I am grateful I found your channel Jo concepts college 4 sal me samjha paya aapne mahine bhar me sikhadi Wish youtube ki bhii koi degree hoti.....Thanks a lot for your efforts
I solved this problem by target sum approach. I just watched your Knapsack video and solved all its variants on my own without watching the rest of your videos! You are great!!
Hey Aditya. First of all, great stuff! Intend to watch this entire series. For this particular problem, I have a doubt: why can't we just try to find x, where x is the largest subset sum possible
Optimized JAVA Solution:) class Solution { public int minDiffernce(int arr[], int N) { int sum = 0; for (int i : arr) sum += i;
int columns = (int) Math.ceil(sum / 2.0); boolean[][] dp = new boolean[N + 1][columns + 1]; for (int k = (int) Math.ceil(sum / 2.0); k > 0; k--) { for (int i = 0; i
He also did the same way just in a different way..he iterated a loop to find min of range-2x..you will iterate a loop to find max of x..and then return range-2x
A little optimized soln similar to yours -> Instead of creating an array to store the last row of dp matrix, 1. create a variable (p) 2. loop through the last row of dp from sum/2 to 0, i.e for(i = sum/2; i >= 0; i--) 3. check if the elem in the dp is 0 or not. If not, then store 'i' in the variable 'p'. 4. return p.
Concept explanation and the way you generalize and basket the problems is amazing. I have watched almost all of your playlists. Absolutely amazing content in each of them 👏.
Amazing explanation!! I addition in the final step to check for value of S1 we can directly do from t[n+1][sum/2] to t[n+1][0] and if we encounter a true we can break out and that is out S1. we can thus return sum - 2s1
Jist of the logic used in the solution (in the end this is quite different from Aditya’s solution, and also more easy to understand):- 1. We need to partition the array into two subsets such that the difference of their sum is minimum. For that, what we have done is first we don’t know what the sum of these two partitions will be, we don’t have any idea about the candidate sums of the subsets of the array. So, first we need to find all the candidate sums. 2. To find all the candidate sums, we know that the minimum sum possible is 0, and the maximum sum possible is the sum of the whole array (which he’s calling as range), all the candidate sums will lie into this range (0-sum). So, after finding the total sum (range), pass this into subset sum function, which will give you a 2D matrix. 3. In this 2D matrix, the last row signifies which number is possible as sum out of all the numbers in the range (0-range), so we’ll only work with the last row of the matrix, true value means this number is making a sum, and a false value means this number is not making a sum. 4. Also notice that in the last row, through the first half of the row, we can retrieve the other half, like range-s1 will give me the value in the other half, and range -2*s1 will give the difference between these two values. Also you can notice that the possibility of minimum difference is more likely in the middle of this last row, because two middle elements are more likely to be close to each other than two elements which are lying at the ends of the row. The difference between these two middle elements is more likely to be less than the difference obtained by a pair which are far from each other. So, what we can do is we can run a loop starting from the middle of the last row to the 0th index of the last row. And then checking if its making a sum (or if it is having a true value), then doing sum-2*s1, which will give me the desired minimum difference. The moment I’ll get this difference I’ll come out of this loop, because if I’ll keep on traversing the backward side, the difference will only increase, because, as I’ll move towards 0th index, I’m encountering a pair which are far from each other, and thus they’ll give me a big difference as compare to a pair which is closer or equal to the middle number. Below is my gfg code:- int minDifference(int arr[], int n) { int sum=0, diff=INT_MAX; for(int i=0;i
One of my friends told me about this channel and he was sure i will learn dp from these videos and boy he was right. i have started forming intuition cause of you. thanks mahn
PYTHON CODE :- def subset(n, k, arr): dp = [[False for j in range(k+1)] for i in range(n+1)] for i in range(n+1): dp[i][0] = True for i in range(1,n+1): for j in range(1,k+1): if arr[i-1]
I used to be afraid of DP and once i saw your videos...my fear turned into interest ...such a crisp-and-clear explanation made me realize that-> fundamentals concepts in mind makes things work so smoothly instead of just mugging up the code
I just think this problem is the exact Knapsack problem 0/1 as here the value array is the weight array itself which means it is the given array of numbers. So, if we just find the (max profit in case of Knapsack) and fill the dp array. Then if we return dp[n][sum/2]. It will give maximum profit which is max possible sum(if we consider value array as a given array of numbers itself) till sum is sum/2. So, just solve it by using Range-2(max sum returned from previous function) just to avoid overhead of storing the last row again to a vector. So, an optimization in terms of space complexity happens here. Anywayss the way you connected the topic is simply amazing!!!
This is the first time i am commenting on any video, just cant stop myself .Your way of teaching is unique from all the TH-camrs and i must say its "BEST". Thank you so much sir :)
Nice video Aditya. Very lucid and natural way to solve the problems. We can optimize the search for for max S1 that minimizes Range - 2*S1. Simply start the loop from half the vector size and iterate towards left. When we get first true, we get the required candidate and we an simply return from the loop. It won't need maintaining a min value variable too.
your explanation and way of teaching is great and the most important thing i like is that on one topic you making a series of video which clear all concept it is just awesome
My approach was slightly different (The concept remains the same) First of all we will find sum of all the elements in the array and divide it by 2. Now, we just have to find a subset whose elements sum upto some value which is closest to the above value we got (sum/2). This is basically a raw 0-1 Knapsack problem now where the value (sum/2) is the maximum capacity of our bag and weights are given in the form of array elements. After we get the maximum closest value from the above algorithm, we can just find our answer by ((sum of all elements) - 2 * maxClosest)
yeah i also solved it in this way, instinctively this is the first solution that comes to mind , i dont know why he didnt adopt this straightforward method.
Honestly speaking, you're videos on dp are the best on youtube. I actually didn't need any help in all of the knapsack variation problems to solve them, because of the way you explained the very first knapsack(basic one) video and the video in which you explained how to recognize and solve a knapsack variation. I wanted to say that it would help a lot if you would write down the constraints as well according to you, so that we could think about the problem accordingly.
Great video Just two things: 1. Instead calculating subset sum for the sum of all values, we can calculate subset sum for sum/2. 2. Instead of creating a vector and iterate through all of its elements, just iterate from last value(sum/2) and if True break because that would be the min diff
Really appreciate your detailed work and effort put behind each video. One question. You loop through the vector from 0 to sum and then find the minimum right. Instead if we reverse the loop to start from mid to zero, the first occurrence of it is the candidate for minimum sum. Am I missing something?
Great work!! I figured out that we can optimize the last step by just considering the last true box from n/2 moving backward. int x = sum/2; while(!t[n][x]) x--; return sum-2*x; This code can be replaced by the last for loop. Although it won't affect the asymptotic time complexity but will definitely contribute to the actual running time of the algo. Ques: What can be done to this code for negative numbers?
This is how teaching should be done!!! Explain the theory in such a way so that one can write the code on his own and can solve all the relevant problems also. You are explaining WHY should we think like this?? Hats of to you Sir!!🔥🔥🔥 In some cases I feel that after seeing the parent problem, we can solve the similar problems with very minimum effort on our own.
Great explanation, Sir... I had just one doubt though... Is there a need to form a vector array ? Can we not use a variable, say v, to store the maximum subset-sum that can exist in the first half of the range and then return (range - 2 * v) ?
Is this pseudocode correct for this problem? arr=[given array of items] arr.sort() //increasing order n=length(arr) a=0 b=0 for i in range(n-1,-1,-1){ // i will reduce by 1 from n-1 to 0 in //each iteration. if (a
nope, this method will fail in some cases of repeated inputs. For eg: if arr = [3,3,3,4,5], we will end up with a = 10, b = 8. So effectively a = 4+3+3=10, and b = 5+3=8. This method will return difference as 2. However, a better split of a = 3+3+3=9 and b=5+4=9 exists, which will return difference as 0.
Aise to ni, bt i guess, after sorting subtract highest no, see diff, repeat till res is -ve, in case of -ve, break the loop and return the res Arr(3 3 3 4 5) Res=18-5 , s2=5, min =res-s2=8 Res=13-4, s2=s2+4, min=res-s2=0 Res=9-3,. s2=s2+3, min=res-s2=-6 Brk the loop, if se phle +ve -ve chk krna h I hope this is correct
subsetsum() can be passed with range/2 Part after subsetsum() can be more optimized: for(j=range/2;j>=0;j--) { if(dp[p][j]==true) { break; } } int answer=range-(2*j); return answer; No need to store in any vector and then find minimum....
I have not seen any one explaining any concepts so well. Content is really organized well. Loved the way you are correlating problems 🙏🙏🙏. Thanks a lot
Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
i bought a course to learn dp and whenever i didnt understand anything i used to come on youtube understand it and then back to the course videos...i dont remember how i landed on ur videos...but after watching ur videos i have not watched any of my course videos...
nice explanation!! hats off!! but we can find answer without even using a vector, just iterate backwards from range/2 unless you find a true cell int s1=range/2; while(dp[n][s1]==false) s1- -; return range-(2*s1); hope it will help.
I have been watching your videos since a couple of days. Your style of teaching is fantastic. I am really enjoying DP. Will be waiting for more videos!!
Bro - i really appreciate the way you presenting the concept....this is really helping to understand concept..Thanks a lot for making these videos and hope expecting more videos like this
Interconnection between the questions is the best part in these tutorials... 😊
note : you may not be able to do this using memoization since all values of lookup table are not filled in memoization , so do this using tabulation since tabulation guarantees that all values of dp table are filled
yeah man found that after an hour of debugging :(
This comment should have more likes
you mean should we use the iterative approach and not the recursive approach?
i done this problem by memoization
Here you go recursion with memoization code --->
class Solution{
public:
int minDiff(int arr[], int n, int lsum, int rsum, vector & dp){
if(n==0) return abs(lsum - rsum);
if(dp[n][lsum]!=-1) return dp[n][lsum];
return dp[n][lsum] = min(minDiff(arr, n-1, lsum-arr[n-1], rsum+arr[n-1],dp), minDiff(arr, n-1, lsum, rsum, dp));
}
int minDifference(int arr[], int n) {
// Your code goes here
int sum = 0;
for(int i=0; i
Thank you very much, Sir, this Q was asked in my Microsft Interview and I was successfully able to clear it .. because I had watched this video once. Thank you again and you're videos are very helpful and awesome.
really?
awesome man
If we can think this, means the trainer is excellent.
hi
😯WOW
referral dede bro
Their are 2 types of Teachers : 1. Who Write code and then explain you 2. Who explain you and then write the code.... The difference is 1st one indirectly wants you to remember the code and 2nd wants you to Develop logic because if u know the logic u can write the code on your own that makes you an independent Guy. Aditya Verma is the 2nd one !! :)))) Nice work...Nice Way of teaching !!
I can say without a doubt that "Aditya Verma is god of DP" 😜. Great Work man!
Yes he is
At least make the 'g' capital! :-)
@@Harish-fx2mo Haha! Similar thing happened with me -- I used "He" (H capital) somewhere in the middle of a sentence and I was rudely reminded that "He" was reserved only for God! :-)
You probably don't know about red coders then
@@zarc5744 it's about the communication.
Seriously I have seen lot of other programming channels on TH-cam.. No one taught the way you did.. Connecting everything..No one can even reach ur level.. Best channel i would say.. Keep uploading.. Waiting for ur recursion and backtracking series.
Today , i realized views can't decide the level of the videos...
Thanks brother, Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
@@TheAdityaVerma please do it asap please
@@TheAdityaVerma Can you please include the explanation of Tree and Graph related concepts too when you get time in the month of May? :)
yes we want videos on graph
@@TheAdityaVerma bhai may aa gaya, graph aur tree ke videos kab aayenge bhai??
Used in LC 1049. Last Stone Weight II
Note to myself: You can start looping over last row dp matrix from range/2 to 0 and choose the first TRUE and BREAK, as first closest sum from the center would be the required sum.
clever approach bro
even i thought the exact same thing !
@@insaneclutchesyt948or do half sum and run on sum/2 , the max value of last index at dp will be the max value possible but less than (if odd) or equal (if even) to the sum/2 , and get the last dp value , do absolute of sum-dpval*2
Actually i am confuse in the subset function, we should make all dp table as true or false, and what we need to return, can you please help me.?
public static boolean subset_sum(int[] arr, int sum, int size)
{
// Table initilization
boolean t[][]= new boolean[size+1][sum+1];
for(int i=0;i
TRY this Leetcode - 2035 (Hard) Acceptance Rate - 19.9%
We can actually reduce the space complexity by half...
One observation is: Since only half of the last line is what we need, we can omit the right half of the matrix. i.e. we can create matrix of size something like.. t[ n+1 ][ ceil(sum/2) ]. And yes I have checked this approach, it works fine.
In this you just need to check the last true in the last row of t matrix. and then desired output is total_sum - 2*(col_num_of_last_true).
In this way, we can further reduce complexity( both time and space ) by not creating unnecessary vectors.
I know ADITYA SIR knows this, he just told you in a way, which a newbie can also understand :)
You can optimize like this for sure. But time complexity will still be the same..in Big O notation ...forget about constant part n = n /2
@@yogesh970 obviously
i am thinking the same.. thanks for the confirmation
@@yogesh970 can you please explain why time complexity will not decrease
@@amansinghgautam9578 because constant multiples don't effect the time complexity on a very big scale
Last part could be solved efficiently: -
int size=v.size(); // v is the vector as mentioned in video
cout
How would you store the last row from table to a vector .....
@@AmandeepSingh-ot6st as mentioned in video
I thought same bro 🙄
Yeah you're right return range - 2*vector[vector.size()-1];
Won't make a difference on the overall complexity so its fine man. This way it is easier to understand for all.
Here is the C++ tabulation code with comments which works perfectly fine:
int minDifference(int arr[], int n) {
int sum = 0;
for(int i = 0; i
Arigato !
thankyou so much buddy for sharing the code , i was getting some errors.
thanks buddy :)
arigato
its not working on leetcode
I really appreciate your work and like your way of explaining this approach. I will just be commenting another approach of doing it using memoization.
Intuition:
1. sum -> sum of all integers in the array
2. partitonOneSum -> the maximum possible sum which is less than or equal to (
Hands down these are the best tutorials for Data Structures and Algorithms out here! This guy helps build up the intuition and concepts like no one else.
Please take note that this strategy only works for an array of elements that are positive. Great job @Aditya, this playlist is very helpful & easy to understand.
When you realize your teacher is teaching the concepts so good that you come up with the approach in 10 mins without seeing the video . I still don't know how i figured out that let's take the sum of the whole array than divide it by 2, and find out the maximum subset sum in the array which is less than or equal to (total_sum/2) and thn take the absolute of total_sum and max_subsetsum.
Thankyou so much @Aditya sir for this greate playlist . You are truely a DP god.
Wow! Great explanation. I am glad that you are explaining how you are developing DP solution rather than filling a table with some formula that most other TH-camrs do when they solve DP problems. After watching those videos I was clueless and frustrated about how the formula shown in those videos was derived. I am glad that I watched your DP Introduction video. After watching 0/1 Knapsack video, I subscribed to your channel because your content is AWESOME! I am pretty sure you will get many subscribers soon. Thank you for taking the time and effort in developing these videos.
I am really glad you noticed the difference between me and other youtubers who just teach for the sake of making videos. Please share and help this channel grow brother !! BTW one question, how did you land on my DP Intro video?
@@TheAdityaVerma For learning DP I watched MIT 6.006 Introduction to Algorithms DP videos (more theoretical but good), Abudul Bari's Algorithm videos (he is pretty good for basics and other algorithms but for DP he also started with filling table) then I tried to solve DP problems on LeetCode and I got stuck so I searched for interview related DP problems and then landed on Tushar Roy DP (garbage explanation), Jenny (table filling only), Back To Back SWE (he explains well but did not link Knapsack variations, not many problems), a few chinese TH-camr videos (difficult to understand as even they were speaking English they were not explaining well) and few other videos and recently 2-3 weeks ago I had seen your channel on TH-cam search for DP videos, I clicked on a random DP video in your DP playlist and did not understand what is going on. Then I was reading comments on Tushar Roy's DP video and there someone shared your DP playlist and said start from the beginning and you wont be disappointed, so I watched your DP Introduction video, then 0/1 Knapsack video and then I realized that your DP videos are the BEST on TH-cam!
@@ankoor did you crack any FANG company ?
@@yadneshkhode3091 Unfortunately not because of speed. I am able to solve problems but I need to work on speed...
@@ankoor ohh me too I am also trying ..
You don't know but you may have revolutionized the way computer programming has always been taught. Your youtube channel is a slap on 99.9% computer programming professors in India.
Please take a series on how to approach ad hoc DP problems. Problems that are not standard. This series is really great and helpful. Thanks!
Thanks, Please share !1
Bhai aise insights na hi top coder na geeksforgeeks na baki ke youtube channels dete hai. Very well explained bro keep doing what you are doing!!
after you get the vector, then the maximum of that vector will always be the answer as in (Range - 2*s1), everything is constant except s1, so to minimize it, we need to choose the largest s1 value.
@@ansumanmishra1757 Can you Please elaborate?
@@ansumanmishra1757 but we want to return only the minimum difference between subsets, so how does it matter if there are repeated numbers in the array?
@@shadowofthecorpse9481 yeah , you are right . My bad. I did a pretty similar problem on codechef where we had to print the total number of such minimum difference. So i messed up . Thanks :)
Yup, no need to find the minimum, just take the last element of vector with half size, that'll be your S1. BTW, Great stuff Aditya!
Ya I was also thinking the same..
What an inordinately terrific teacher...Love you man :)
Bro only one line can describe you "Everybody is a gangster until a real gangster walks into the room"
summing up what we did is the best part of these tutorials which a lot of youtubers and even paid course's teachers miss out on. Seeing 40+ min video tutorials can make anyone forget small details but summing up what we did after each new step is the best thing that you have done.
Another approach that one can observe from this is, to minimize range - 2*S1 we need to maximize S1. Also, S1 is less than range/2 so we can just use the Knapsack directly with weight array as given array and value array also as given array but the capacity of the knapsack as range/2. This finds the maximum subset-sum below range/2. Thus, we can just return range - 2*S1 directly. This reduces the space complexity by half.
excellent concept bro
@@pratyushnarain5220 the weight array should be the, sums array of range/2 na?
That's how I approach at first too.
Best explanation to a DP problem i have seen till now
Very nice way of explaining.. thanks a lot for making this series. Its very helpful for people like me who are preparing for intern interviews. Please make a similar series on graphs and heaps also.. And please try to make videos shorter (around 15 mins)
Heap is already there brother, check out my channel !!
WOAHHHHHHHHHHH
I was able to solve the question just seeing the video till 6:04
Brute Force:
Make all subsequence but that will result in time complexity of exponential
In brute force, once you have made all the subsequence you just need to accumulate that particular subsequence and take a remainder as the total sum-sum of accumulated subsequence.
After that make a variable ans = INT_MAX and put the minimum of total-remaining.
Optimized:
Try thinking of subset-sum where we take sum as the total sum of all the numbers in the array.
Time Complexity = O(n*total)
where total = sum of all the elements in the array.
C++ Code :
int minDifference(int arr[], int n) {
int total = accumulate(arr, arr+n, 0LL),ans = INT_MAX, dp[n+1][total+1],remaining;
memset(dp,0,sizeof(dp));
for(int i=0;i
At 40:23 do we need to iterate throughout the vector? Just substracting it twice of last element of the vector can give the minimum, as created vector will hold the maximum value at the last index and to minimize, we should substract maximum from the range
Yeah you're right
I came to comment the same dude 😂😂😂 @Aditya Verma should pin this.
I started reading the comments before watching this video and it got me intimidated at first but the way you explain is so smooth, that I reach to solution before you show on the lecture. Kudos to the work you have done.
I dont't know how to appreciate you !!!! , Just Awesome
Thnaks brother !!
words cant describe how much happy i am that i came across your channel !you are really doing a great job ! your methods of approaching the problem are so good .you are actually teaching how to approach the problem and that is what sets you apart from the rest of the channels on TH-cam !thank you so much !saw your profile on linked in and directly sent you a connection request would be really happy if you accept it !!! thank you again !
Thanks Lakshya, and you meant linkedIN right and not linked list?! 😂
Do subscribe and share the content to help the channel grow !!
@@TheAdityaVerma 😂😂😂yeah ! Sorry typo*😂😂😂
I Madara Uchiha declare you the best DP teacher.
theek
I approached this problem like a 0-1 knapsack problem, except that value array and weight array both are same and you have to maximize value while keeping the weight below total/2. Made it much easier to understand.
While using the bottom up approach(Tabulation) isn't it enough to construct the boolean table until (sum/2 ) instead of constructing the table until (sum)?
In the end all we care about is the value closest to (sum/2) right?
You're right
Also you dont need to make extra vector. Just start from sum/2 towards 0 and first true value will be the required s1
@@manavmohata1240 yup
Yes, minimum of range - 2s1 can be written as maximizing s1
Taking minimum can be visualised in a number line as the distance between 2 points ie, S1 and S2 should be minimum. Which makes the s1 that is closer to center minimum.
This playlist is pure gold. much much better than paid courses.
Bhaiya bohot ache see samjh aa gya DP ... Aaj tak aisa ache see kissine nhi samjhaya... thanks a lot for ♥️ please upload regular Bhai..appko bohot support karenge...log paise leke bhi itna acha nahi sikhate thanks again @aditya Bhai 💝
Best explaination . Can't compare your teaching with others .
Only thank you is very less for your efforts .❤️❤️
this is the only channel that I actually recommend to people irl
Hi Aditya, nice lecture series. Its the first DP series i have started watching and with every upload i m still interested in watching. great work
Also quick question, could you mention what would be the changes in case of negative values present in the array for minimum subset sum difference. thx!
Loved the way he solved all the questions just using a single concept we have to understand the question only, we already knew its answer.
This might help you guys.
CODE:-(NO need to take a vector for all possible sum just take the last value.)
vector dp(n + 1 , vector(sum / 2 + 1 , false));
for (int i = 0 ; i < n + 1 ; i++) {
dp[i][0] = true;
}
for (int i = 1 ; i < n + 1 ; i++) {
for (int j = 1 ; j < sum / 2 + 1; j++) {
if (arr[i - 1]
bhai runtime error arha tha mera toh. similar hi kiya tha maine bhi
bhai thik hua runtime tera??? @@mohdfaisalquraishi8675
Good...Nice !!
@@mohdfaisalquraishi8675 agar range negative hoga to runtime error aayega. Leetcode me arr[i] negative bhi hai.
@@mohdfaisalquraishi8675 for last loop we can reduce time complexity , because we know that its always first element coming from right side(from totalsum/2) which is true, that will be our answer, here is the most optimized code. No need even vector/list , no need to traverse dp from front to tsum/2, we can traverse in reverse direction, get first true element in dp, and get min sum using return (tsum-2*j)
public int minDifference(int nums[], int n) {
// tsum means = total sum
int tsum = 0;
for(int i=0;i
sir aapse better dp phadane wala nhi dekha aajtak you are really great, jo pattern badi badi organizations nhi samjhpati aap samjhate ho great sir
Please it's a request. make videos on Graph related questions! and cover topics like dfs, bfs
yes bhaiya please
for(i=0; ;i++)
{
cout
@@ViralAgrawal12321 Time limit exceeded!😂
@@a.yashwanth 😂
Thank you Aditya bhai.......I am grateful I found your channel
Jo concepts college 4 sal me samjha paya aapne mahine bhar me sikhadi
Wish youtube ki bhii koi degree hoti.....Thanks a lot for your efforts
One of the best places to learn DP. Great explanation of the logic behind rather than just writing the code. Thanks for being such a great teacher,
I solved this problem by target sum approach. I just watched your Knapsack video and solved all its variants on my own without watching the rest of your videos! You are great!!
Hey Aditya. First of all, great stuff! Intend to watch this entire series. For this particular problem, I have a doubt: why can't we just try to find x, where x is the largest subset sum possible
exactly like 0/1 Knapsack..
Yes, we can do that.. It is much much simpler
Optimized JAVA Solution:)
class Solution
{
public int minDiffernce(int arr[], int N)
{
int sum = 0;
for (int i : arr)
sum += i;
int columns = (int) Math.ceil(sum / 2.0);
boolean[][] dp = new boolean[N + 1][columns + 1];
for (int k = (int) Math.ceil(sum / 2.0); k > 0; k--) {
for (int i = 0; i
He also did the same way just in a different way..he iterated a loop to find min of range-2x..you will iterate a loop to find max of x..and then return range-2x
This playlist follows DP. Great Work Man. Great Work. Kudos.
Just fall in love with DP ❤. Thanks a lot sir. Make more tutorials on competitive coding. 🧡🧡
A little optimized soln similar to yours ->
Instead of creating an array to store the last row of dp matrix,
1. create a variable (p)
2. loop through the last row of dp from sum/2 to 0, i.e for(i = sum/2; i >= 0; i--)
3. check if the elem in the dp is 0 or not. If not, then store 'i' in the variable 'p'.
4. return p.
Concept explanation and the way you generalize and basket the problems is amazing.
I have watched almost all of your playlists. Absolutely amazing content in each of them 👏.
Amazing explanation!!
I addition in the final step to check for value of S1 we can directly do from t[n+1][sum/2] to t[n+1][0] and if we encounter a true we can break out and that is out S1. we can thus return sum - 2s1
Jist of the logic used in the solution (in the end this is quite different from Aditya’s solution, and also more easy to understand):-
1. We need to partition the array into two subsets such that the difference of their sum is minimum. For that, what we have done is first we don’t know what the sum of these two partitions will be, we don’t have any idea about the candidate sums of the subsets of the array. So, first we need to find all the candidate sums.
2. To find all the candidate sums, we know that the minimum sum possible is 0, and the maximum sum possible is the sum of the whole array (which he’s calling as range), all the candidate sums will lie into this range (0-sum). So, after finding the total sum (range), pass this into subset sum function, which will give you a 2D matrix.
3. In this 2D matrix, the last row signifies which number is possible as sum out of all the numbers in the range (0-range), so we’ll only work with the last row of the matrix, true value means this number is making a sum, and a false value means this number is not making a sum.
4. Also notice that in the last row, through the first half of the row, we can retrieve the other half, like range-s1 will give me the value in the other half, and range -2*s1 will give the difference between these two values. Also you can notice that the possibility of minimum difference is more likely in the middle of this last row, because two middle elements are more likely to be close to each other than two elements which are lying at the ends of the row. The difference between these two middle elements is more likely to be less than the difference obtained by a pair which are far from each other. So, what we can do is we can run a loop starting from the middle of the last row to the 0th index of the last row. And then checking if its making a sum (or if it is having a true value), then doing sum-2*s1, which will give me the desired minimum difference. The moment I’ll get this difference I’ll come out of this loop, because if I’ll keep on traversing the backward side, the difference will only increase, because, as I’ll move towards 0th index, I’m encountering a pair which are far from each other, and thus they’ll give me a big difference as compare to a pair which is closer or equal to the middle number.
Below is my gfg code:-
int minDifference(int arr[], int n) {
int sum=0, diff=INT_MAX;
for(int i=0;i
very well explained
One of my friends told me about this channel and he was sure i will learn dp from these videos and boy he was right. i have started forming intuition cause of you. thanks mahn
Thank you for evolving our brains :)😂
😂😂😂😂😂😂😂😂 Evolution is natural ✌️
@@TheAdityaVerma are you on twitter?
I have not seen such an enthusiastic teacher.
No words bro
To appreciate...
Keep going
Thank you, I will
Your channel is so underrated. I really appreciate your work. Thanks a lot :D
PYTHON CODE :-
def subset(n, k, arr):
dp = [[False for j in range(k+1)] for i in range(n+1)]
for i in range(n+1):
dp[i][0] = True
for i in range(1,n+1):
for j in range(1,k+1):
if arr[i-1]
I used to be afraid of DP and once i saw your videos...my fear turned into interest ...such a crisp-and-clear explanation made me realize that-> fundamentals concepts in mind makes things work so smoothly instead of just mugging up the code
Small doubt, instead of iterating through the vector, can we simply take mn=Range-2*v[v.size()-1] for the minimum value?
Yes we can do that :) sorry I'm watching after 3years
I just think this problem is the exact Knapsack problem 0/1 as here the value array is the weight array itself which means it is the given array of numbers. So, if we just find the (max profit in case of Knapsack) and fill the dp array. Then if we return dp[n][sum/2]. It will give maximum profit which is max possible sum(if we consider value array as a given array of numbers itself) till sum is sum/2. So, just solve it by using Range-2(max sum returned from previous function) just to avoid overhead of storing the last row again to a vector. So, an optimization in terms of space complexity happens here.
Anywayss the way you connected the topic is simply amazing!!!
Looking for this comment for so long lol. Thought about this approach only
Ye dislike vhi kerte hai jo pichle videos dekhe bina direct ish video per aate hai!!!
This is the first time i am commenting on any video, just cant stop myself .Your way of teaching is unique from all the TH-camrs and i must say its "BEST". Thank you so much sir :)
Please try to make videos shorter(around 15mins).
Btw you're a great teacher.
yeah! No need to repeat the explanation, Because it is a video one can go back and watch again if he/she is getting it.
Nice video Aditya. Very lucid and natural way to solve the problems.
We can optimize the search for for max S1 that minimizes Range - 2*S1. Simply start the loop from half the vector size and iterate towards left. When we get first true, we get the required candidate and we an simply return from the loop. It won't need maintaining a min value variable too.
This code is not dealing negative numbers!!! Would u please help?
your explanation and way of teaching is great
and the most important thing i like is that on one topic you making a series of video which clear all concept it is just awesome
My approach was slightly different (The concept remains the same)
First of all we will find sum of all the elements in the array and divide it by 2.
Now, we just have to find a subset whose elements sum upto some value which is closest to the above value we got (sum/2).
This is basically a raw 0-1 Knapsack problem now where the value (sum/2) is the maximum capacity of our bag and weights are given in the form of array elements.
After we get the maximum closest value from the above algorithm, we can just find our answer by ((sum of all elements) - 2 * maxClosest)
yeah i also solved it in this way, instinctively this is the first solution that comes to mind , i dont know why he didnt adopt this straightforward method.
@@ammarranapur5917 can you please provide the code that you solved for this problem!!
If y'all have solved this way could you please provide the code
Honestly speaking, you're videos on dp are the best on youtube. I actually didn't need any help in all of the knapsack variation problems to solve them, because of the way you explained the very first knapsack(basic one) video and the video in which you explained how to recognize and solve a knapsack variation. I wanted to say that it would help a lot if you would write down the constraints as well according to you, so that we could think about the problem accordingly.
Really amazing. Never thought like this :) Would be great if you can explain time complexity at the end.
P.S. Looking forward for many more videos!
Great video
Just two things:
1. Instead calculating subset sum for the sum of all values, we can calculate subset sum for sum/2.
2. Instead of creating a vector and iterate through all of its elements, just iterate from last value(sum/2) and if True break because that would be the min diff
I had the same intuition about the problem. 😄
Really appreciate your detailed work and effort put behind each video.
One question. You loop through the vector from 0 to sum and then find the minimum right. Instead if we reverse the loop to start from mid to zero, the first occurrence of it is the candidate for minimum sum. Am I missing something?
No, this approach is also fine.
At 11:50 I got the solution. Awesome approach. This is how hints work in interview. You gave me first hint and I solved it.
Why we have to run that last loop when you get highest value of s1?
We can simply put that formula(min difference= range -2*s1)
yes same qs?
The given initial array may have negative integers so the for loop is needed to find maximum s1 in the vector array.
Hats off!!!!!!! No words to say. No man can give such a great content even after taking money!
Great work!! I figured out that we can optimize the last step by just considering the last true box from n/2 moving backward.
int x = sum/2;
while(!t[n][x]) x--;
return sum-2*x;
This code can be replaced by the last for loop. Although it won't affect the asymptotic time complexity but will definitely contribute to the actual running time of the algo.
Ques: What can be done to this code for negative numbers?
Ya somene plz tell what should be done in case of negative numbers in array....leetcode ques no. 2035
This is how teaching should be done!!! Explain the theory in such a way so that one can write the code on his own and can solve all the relevant problems also. You are explaining WHY should we think like this?? Hats of to you Sir!!🔥🔥🔥 In some cases I feel that after seeing the parent problem, we can solve the similar problems with very minimum effort on our own.
Great explanation, Sir... I had just one doubt though... Is there a need to form a vector array ? Can we not use a variable, say v, to store the maximum subset-sum that can exist in the first half of the range and then return (range - 2 * v) ?
Yeah ofcourse you can do this. Aditya just did it for the students to make it more understandable .
One thing i can clearly say that u are very much passionate to teach others.
Is this pseudocode correct for this problem?
arr=[given array of items]
arr.sort() //increasing order
n=length(arr)
a=0
b=0
for i in range(n-1,-1,-1){
// i will reduce by 1 from n-1 to 0 in
//each iteration.
if (a
nope, this method will fail in some cases of repeated inputs. For eg: if arr = [3,3,3,4,5], we will end up with a = 10, b = 8. So effectively a = 4+3+3=10, and b = 5+3=8. This method will return difference as 2.
However, a better split of a = 3+3+3=9 and b=5+4=9 exists, which will return difference as 0.
@@shadowofthecorpse9481 hmmm😐 It's not working in repeated cases... Anyways, Thanks for correction 🙂
Aise to ni, bt i guess, after sorting subtract highest no, see diff, repeat till res is -ve, in case of -ve, break the loop and return the res
Arr(3 3 3 4 5)
Res=18-5 , s2=5, min =res-s2=8
Res=13-4, s2=s2+4, min=res-s2=0
Res=9-3,. s2=s2+3, min=res-s2=-6
Brk the loop, if se phle +ve -ve chk krna h
I hope this is correct
Probably nobody other than you can explain so smoothly such an important concept..Thanks For Sharing your wonderful knowledge ✨
subsetsum() can be passed with range/2
Part after subsetsum() can be more optimized:
for(j=range/2;j>=0;j--)
{
if(dp[p][j]==true)
{
break;
}
}
int answer=range-(2*j);
return answer;
No need to store in any vector and then find minimum....
Good job
Bro you are pro....even i was thinking the same😅
I have not seen any one explaining any concepts so well. Content is really organized well. Loved the way you are correlating problems 🙏🙏🙏. Thanks a lot
thank u for so much effort
Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
i bought a course to learn dp and whenever i didnt understand anything i used to come on youtube understand it and then back to the course videos...i dont remember how i landed on ur videos...but after watching ur videos i have not watched any of my course videos...
having pain in my head.oh wait my brain is evolving
lmaaoo
Thanks bhaiya, it's the first time I coded any hard problem on gfg by myself completely and got it correct. Only because of you.
Cracked version download kar le bhai watermark nahi aaega ,
or is comment mai ID meri hai words mere friend ke hai.
THANK U BRO!
bhai crack version link ????
@@adityakhare9577 bhai isne link upload off kr rkha hai, kya kren aap btao?
@@ishitamishra6279 all copyrights reserved by abdul pandat.
@@ishitamishra6279 sed lyfe😑
This channel is underrated...I want aditya to work on this full time for which he'll be requiring ur support..Please share in each and every group
just stumbled on this playlist, now I'm going to watch it complete. Awesome way of teaching. Stay motivated and keep making such videos.
nice explanation!! hats off!!
but we can find answer without even using a vector, just iterate backwards from range/2 unless you find a true cell
int s1=range/2;
while(dp[n][s1]==false)
s1- -;
return range-(2*s1);
hope it will help.
I have been watching your videos since a couple of days. Your style of teaching is fantastic. I am really enjoying DP. Will be waiting for more videos!!
Brilliant.
If u didn't understand in the starting wait till the end of the video , u will get it.
One of the Best Teacher in the world.
Hats off to the way you build the intuition and relate the problem to another already known problem.....Amazing explanation bro. Thanks a lot.
The way you approach the problem is to be appreciated. And You make me understand better than any one else. Thank you bro !!
Your DP playlist is itself a DP
Bro - i really appreciate the way you presenting the concept....this is really helping to understand concept..Thanks a lot for making these videos and hope expecting more videos like this
Sir ji Tussi great ho 😎😉😘. Simplest explanation . If someone is not getting this then he has to forget about programming.