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
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 !! ✌️❤️
Seriously I have seen lot of other programming channels on RUclips.. 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.
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.
@@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! :-)
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 !!
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 :)
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.
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.
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.
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 (
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 :)
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
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.
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.
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.
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 RUclipsrs 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 RUclipsr 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 RUclips 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 RUclips!
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.
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 RUclips !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 !
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
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.
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)
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!!
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 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.
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
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
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
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
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 👏.
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 💝
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.
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!
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
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
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.
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 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...
So, I tried solving this problem myself with a complete different logic, which i can say is quite less complicated, after i got to know that the solution resonates with that of equal sum partition. In my code, I've applied that :- 1) if the sum of whole array is even, then the possible least difference is 0, if that array can be divided into equal sum partition. If the array cannot be divided into equal sum partition, then the next minimum difference can be 2, and then 4,6 and so on. So,I intialized the difference as 0( best case), and then applied subset sum function to check if equal sum partition exists or not. If it exists then cool, return difference as 0. If it does not exists, call the function recursively by sum=sum-1 and count=count+2. And so on keep on checking , you'll definitely land up to an answer. 2) same for odd sum, initialize the count as 1, and then apply the subset sum function for sum=sum/2,if the subset sum funtion returns true for this sum, then just return 1, and if it does not return true, then call the funtion recursively with now sum=sum-1,it will return 3 (which is the next minimum difference) and then keep on checking it by running the function recursively. Here's my code: #include using namespace std; int func(int ar[], int n, int sum, int count) { int t[n + 1][sum + 1]; for (int i = 0; i < sum + 1; i++) t[0][i] = 0; for (int i = 0; i < n + 1; i++) t[i][0] = 1; for (int i = 1; i < n + 1; i++) { for (int j = 1; j < sum + 1; j++) { if (ar[i - 1]
Initially, I solved with this method but after watching the complete video I realized that we do not need to call the function again because we can directly check dp[n][sum-1] is either true or not. So, basically answer lies in the last row of the dp matrix and we do not have to create it again and again.
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 the first time i am commenting on any video, just cant stop myself .Your way of teaching is unique from all the RUclipsrs and i must say its "BEST". Thank you so much sir :)
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
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?
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....
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 !! ✌️❤️
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.
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) ?
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
We can actually skip the last step(storing values of last column in array and computing minimum). For (Range - 2*S1) to be minimum the S1 value should be largest so we can iterate over the last row of dp and get the last possible index < range/2. Then we can just return ans as (Sum - 2*ind). In Code this should translate to this. class Solution{ public: int minDifference(int arr[], int n) { int sum = 0; sum = accumulate(arr, arr+n, sum); bool dp[n+1][sum+1];
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
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.
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!!
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.
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
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??
Seriously I have seen lot of other programming channels on RUclips.. 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.
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
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.
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 !!
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
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.
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
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
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.
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.
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 (
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..
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
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.
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.
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.
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 RUclipsrs 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 RUclipsr 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 RUclips 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 RUclips!
@@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.
Bro only one line can describe you "Everybody is a gangster until a real gangster walks into the room"
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 RUclips !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 dont't know how to appreciate you !!!! , Just Awesome
Thnaks brother !!
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
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.
What an inordinately terrific teacher...Love you man :)
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 !!
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!!
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]
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!!
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 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.
Best explaination . Can't compare your teaching with others .
Only thank you is very less for your efforts .❤️❤️
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.
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 😂
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 Madara Uchiha declare you the best DP teacher.
theek
Best explanation to a DP problem i have seen till now
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
This playlist follows DP. Great Work Man. Great Work. Kudos.
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.
This playlist is pure gold. much much better than paid courses.
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
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 👏.
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 💝
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.
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!
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
Thank you for evolving our brains :)😂
😂😂😂😂😂😂😂😂 Evolution is natural ✌️
@@TheAdityaVerma are you on twitter?
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.
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
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
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
Your channel is so underrated. I really appreciate your work. Thanks a lot :D
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
this is the only channel that I actually recommend to people irl
Ye dislike vhi kerte hai jo pichle videos dekhe bina direct ish video per aate hai!!!
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
No words bro
To appreciate...
Keep going
Thank you, I will
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...
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.
Hands down brother...
No one can explain better than this....👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍
This code is not dealing negative numbers!!! Would u please help?
So, I tried solving this problem myself with a complete different logic, which i can say is quite less complicated, after i got to know that the solution resonates with that of equal sum partition.
In my code, I've applied that :-
1) if the sum of whole array is even, then the possible least difference is 0, if that array can be divided into equal sum partition. If the array cannot be divided into equal sum partition, then the next minimum difference can be 2, and then 4,6 and so on. So,I intialized the difference as 0( best case), and then applied subset sum function to check if equal sum partition exists or not. If it exists then cool, return difference as 0. If it does not exists, call the function recursively by sum=sum-1 and count=count+2. And so on keep on checking , you'll definitely land up to an answer.
2) same for odd sum, initialize the count as 1, and then apply the subset sum function for sum=sum/2,if the subset sum funtion returns true for this sum, then just return 1, and if it does not return true, then call the funtion recursively with now sum=sum-1,it will return 3 (which is the next minimum difference) and then keep on checking it by running the function recursively.
Here's my code:
#include
using namespace std;
int func(int ar[], int n, int sum, int count)
{
int t[n + 1][sum + 1];
for (int i = 0; i < sum + 1; i++)
t[0][i] = 0;
for (int i = 0; i < n + 1; i++)
t[i][0] = 1;
for (int i = 1; i < n + 1; i++)
{
for (int j = 1; j < sum + 1; j++)
{
if (ar[i - 1]
Initially, I solved with this method but after watching the complete video I realized that we do not need to call the function again because we can directly check dp[n][sum-1] is either true or not. So, basically answer lies in the last row of the dp matrix and we do not have to create it again and again.
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.
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 the first time i am commenting on any video, just cant stop myself .Your way of teaching is unique from all the RUclipsrs and i must say its "BEST". Thank you so much sir :)
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!
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
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.
This playlist is 24K gold!... too good.
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😅
Probably nobody other than you can explain so smoothly such an important concept..Thanks For Sharing your wonderful knowledge ✨
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 !! ✌️❤️
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.
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 .
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. 😄
having pain in my head.oh wait my brain is evolving
lmaaoo
We can actually skip the last step(storing values of last column in array and computing minimum). For (Range - 2*S1) to be minimum the S1 value should be largest so we can iterate over the last row of dp and get the last possible index < range/2. Then we can just return ans as (Sum - 2*ind).
In Code this should translate to this.
class Solution{
public:
int minDifference(int arr[], int n) {
int sum = 0;
sum = accumulate(arr, arr+n, sum);
bool dp[n+1][sum+1];
for(int i=0;i
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
I have not seen such an enthusiastic teacher.
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😑
Brilliant.
If u didn't understand in the starting wait till the end of the video , u will get it.
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.
Your DP playlist is itself a DP
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.
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 !!
Great teaching. You are very good in interconnecting things and making things very easy to understand.
One thing i can clearly say that u are very much passionate to teach others.
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.
One of the Best Teacher in the world.
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!!
just stumbled on this playlist, now I'm going to watch it complete. Awesome way of teaching. Stay motivated and keep making such videos.
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.