yes, by taking dp[n+1][sum/2+1] we can reduce the time complexity. I guess he just wanted to explain in a way everyone understands the concept behind it and that's why he took dp[n+1][sum]
Since we are considering that s1 < s2, will it make sense instead of taking the weight range 0 - 11, we just take 0 - 5? Since it seems that at the end we will use the last for column 0 - 5 only?
You are absolutely correct. It would reduce the space complexity as well as the time complexity to half of the original and of course it would still work.
a small optimization, instead of constructing N*W array its enough to construct N*ceil(W/2) and check last row from last column and if it's true then min-difference=abs(i-(W-i)) where i is the column index, W is sum, happy coding :)
Thanks for the clarifications and the code example! I first got the wrong value, but I did a mistake , if I want to get the two optimal pair of values then I need the "i" value instead of diff, or you can return both the i and diff. I use PHP, so it will be: $value = 0; for ($i=0; $i abs($first-$second)){
In the code I have simplified. If you closely look at first and second then first is S1 and second is (SUM-S1). If you subtract them then it will be (SUM-2*S1). They both are exactly the same.
In the code when you try to find the minimum difference value, you iterate from 0 to sum/2. I its not always the result in the True value that is closest to the sum/2 ? i= sum//2 while not dp[n][i]: i-=1 diff= sum-2*i if i is closer to sum/2 the difference is minimized, therefore we only neet to find the column with True value closer to sum/2.
So if we want to solve this question using recursion then we have to apply subset sum solution for 0 to sum/2 and then we have to find the minimum of them after putting them in this formula:- (sum - 2(answer of each subset sum problem))?
It's already in the playlist and numbering will hamper me from adding new videos randomly and shuffling part. Moreover, those who want to learn just particular videos will not feel comfortable if I number them.
@@techdose4u I have a suggestion: Instead of numbering, you can categorize them into DP patterns. e.g. ks-01 from knapsack 0/1, ks-INF (knapsack infinity), Partition (e.g. MCM, eggdrop), etc. so that students can see the similarity in code within a given pattern. Thanks!
You can use short array as well treat 0 as false and 1 as true. Also we can optimise the solution using 1D tabular dp just like sunset sum. Also solving only till sum/2 is enough
hey your code is not working on leetcode def minimumDifference(self, nums) : n = len(nums) sum = 0 for i in range(n): sum += nums[i] dp = [[False]*(sum+1) for i in range(n+1)] for i in range(n+1): for j in range(sum+1): if j == 0: dp[i][j] = True elif i == 0: dp[i][j] = False elif nums[i-1]>j: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]] diff = float('inf') for i in range(sum//2+1): first = i second = sum-i if dp[n][i] == True and diff>abs(first-second): diff = abs(first-second) return diff
Firstly thank you very much for this whole DP series. It is extremely helpful. Secondly, I have a small doubt. If I know that my subset S1 can have maximum sum as S/2 only, I can find the maximum sum S1 can have(like max profit in 0/1 knapsack). In that case we will store max sum possible and not T/F in the DP table. Is this approach fine? I solved the interview bit problem like this, but wanted to know from you if thinking this way is fine too
We can reduce time by creating a dp[n+1][sum/2+1]. Thanks sir, it worked because u explained so well.
Nice 👍🏼
Yes I did it that way too. All thanks goes to sir.
@@suvamroy6205 👍🏼
I was thinking the same thing @Aditya Ohja
We can also iterate from backwards i.e. for(int i = sum/2 ; i>=0 ;i--) in the last step.
You have a great voice which makes us pay detail attention to what you're saying . Thank you for such excellent series. Very engaging!
Looks like I should apply for singing 😂
@Andrew Kaison HAHAHA
It was so good, I slept while listening to him,
@pooja gattiga chaduvtav.
Firstly, thank you so much for doing these videos. Much appreciated!
Question:
Set S is divided to S1, S2. We are calculating only for S1, which is
yes, by taking dp[n+1][sum/2+1] we can reduce the time complexity. I guess he just wanted to explain in a way everyone understands the concept behind it and that's why he took dp[n+1][sum]
What if negative elements are there?
great work sir. for all your videos, before watching till the end, i hit like cz i know it will be awesome and simple to understand : )
It is not one of the best explanation, but it is the best explanation. Thank you🙏
Thanks for the appreciation :)
Thanks! Very well explained. Knowledge of solving 'Subset sum' (links in desc) is a pre-req for this.
Great explaination sir
Thank You
Welcome :)
Since we are considering that s1 < s2, will it make sense instead of taking the weight range 0 - 11, we just take 0 - 5? Since it seems that at the end we will use the last for column 0 - 5 only?
You are absolutely correct. It would reduce the space complexity as well as the time complexity to half of the original and of course it would still work.
Yes.... you are correct.
This idea came to me too. Was just about to ask and verify
@@avinashjha4887 Space Complexity wont decrease but space will decrease
a small optimization, instead of constructing N*W array its enough to construct N*ceil(W/2) and check last row from last column and if it's true then min-difference=abs(i-(W-i)) where i is the column index, W is sum, happy coding :)
That's what I wanted
Thanks for video! I guess it’s tricky to see this as a variation of can we divide the array into 2 equal sum subset question.
Welcome
Nailed it sir 🔥🔥🔥
sir, one thing i didn't understand, we are checking for dp[n][i]==True condition , how can one be sure that dp[n][sum-i] will also be true??
thank you so much sir for such a great explanation...really it was very much helpful thanks a lot sir...
you know you've been watching too many tech dose videos when you know the answer the moment he says "it's a variation of ... problem". LOL thanks
What about an array of negative and positive integers. Would dp be able to solve this efficiently?
Thanks for the clarifications and the code example!
I first got the wrong value, but I did a mistake , if I want to get the two optimal pair of values then I need the "i" value instead of diff, or you can return both the i and diff.
I use PHP, so it will be:
$value = 0;
for ($i=0; $i abs($first-$second)){
//get value
$value = $i;
$diff = abs($first-$second);
}
}
return [
'value' => $value,
'diff' => $diff,
];
extraordinary explanation. Keep it up, mate.
sir u are great....continue
Sure :)
You can use 1D array to do that, no need for 2D tho.
Yea :)
How do you go back and look up the true/false values?
Can you link to any example of this?
@@nemnoton Just iterate over the last row, by keeping row no. constant.
fantastic explanation
Thanks for video..osssum
Hi Sir, What if the input contains negative numbers too? I see the solution would not consider negative number in the input array
Exactly what I am trying to find the solution for, I guess in Negative numbers we cant really use this approach
Good one!
Keep it up
Thanks 😊
sir,you have explained diff=sum-2s1
but in the code abs(first-second)
can we use any of the above statements?
and overall amazing explanation
In the code I have simplified. If you closely look at first and second then first is S1 and second is (SUM-S1). If you subtract them then it will be (SUM-2*S1). They both are exactly the same.
@@techdose4u thanks sir
Welcome
Great work!!!!!!!!!
In the code when you try to find the minimum difference value, you iterate from 0 to sum/2. I its not always the result in the True value that is closest to the sum/2 ?
i= sum//2
while not dp[n][i]:
i-=1
diff= sum-2*i
if i is closer to sum/2 the difference is minimized, therefore we only neet to find the column with True value closer to sum/2.
So if we want to solve this question using recursion then we have to apply subset sum solution for 0 to sum/2 and then we have to find the minimum of them after putting them in this formula:- (sum - 2(answer of each subset sum problem))?
Thank you for the video. For some reason, this code does not work for some inputs like: [76,8,45,20,74,84,28,1]
We can solve Leetcode 1049 last stone weight 2 by this approach...
Can you try adding serial numbers to this dp series and make a playlist?
Thanks 👍🏻
It's already in the playlist and numbering will hamper me from adding new videos randomly and shuffling part. Moreover, those who want to learn just particular videos will not feel comfortable if I number them.
@@techdose4u okay, thanks bro 👍🏻
@@techdose4u I have a suggestion: Instead of numbering, you can categorize them into DP patterns. e.g. ks-01 from knapsack 0/1, ks-INF (knapsack infinity), Partition (e.g. MCM, eggdrop), etc. so that students can see the similarity in code within a given pattern. Thanks!
@@0anant0 yea. That I am doing. I am covering in order and later when I include more videos then I will insert them in order.
@@techdose4u Thanks! Your videos are very helpful - I watch them everyday :-)
if nums[i] is negative then how to proceed?..in the leetode qn constraint its negative
bro, can we do it using int[][] dp not by boolean[][] dp??
Yep
@@techdose4u can you please explain it little bit.
You can use short array as well treat 0 as false and 1 as true. Also we can optimise the solution using 1D tabular dp just like sunset sum. Also solving only till sum/2 is enough
how deal if array has negative elements
man , why do you waste others time by putting the solution that doesnt work?? check on leet code, the -36,36 test case is not working
In case of negative values it will fail as array can not have negative index.
hey your code is not working on leetcode
def minimumDifference(self, nums) :
n = len(nums)
sum = 0
for i in range(n):
sum += nums[i]
dp = [[False]*(sum+1) for i in range(n+1)]
for i in range(n+1):
for j in range(sum+1):
if j == 0:
dp[i][j] = True
elif i == 0:
dp[i][j] = False
elif nums[i-1]>j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
diff = float('inf')
for i in range(sum//2+1):
first = i
second = sum-i
if dp[n][i] == True and diff>abs(first-second):
diff = abs(first-second)
return diff
Your code will set false at dp[0][0] which is not right , according to the theory part
Firstly thank you very much for this whole DP series. It is extremely helpful. Secondly, I have a small doubt. If I know that my subset S1 can have maximum sum as S/2 only, I can find the maximum sum S1 can have(like max profit in 0/1 knapsack). In that case we will store max sum possible and not T/F in the DP table. Is this approach fine? I solved the interview bit problem like this, but wanted to know from you if thinking this way is fine too
Yes. You can store the max amount. Perfectly fine :)
@@techdose4u Thank you :D
How this is different from leetcode 2035 ?
Leetcode 2035 : Partition array into two arrays to minimize the difference
can we fill the dp table using recursion
That's memoization.
@@techdose4u yes pls explain this method or else just type the code
@@techdose4u pls just type the code sir please :(
@@techdose4u why are u not replying sir
What if S1 is found after half ?
S1 represents the smaller partition so it has to be
19th line:
What if (j - A[i] < 0)?
We'd get a Segmentation Fault;
this approach is not working for negative numbers
bro what if the numbers are negative
why this code gives runtime error-class Solution {
public:
int minimumDifference(vector& nums) {
int sum=0;
int n=nums.size();
for(int it:nums){
sum+=it;
}
vectordp(n+2,vector(sum+2));
for(int i=0;i
Please make a roadmap for fresher (batch 2020)to crack google in 6months for a DSA beginner