I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you. Keeping a like target of 500 ❤✌🏼

@divyaporwal589

2 жыл бұрын

It is not working with negative numbers, for example the array is -36,36 and then the target is zero

@harshitrawat138

2 жыл бұрын

@@divyaporwal589 Dp requires array and array can't have negative indexes. If array contains negative numbers you can subtract the most negative number of given array (minx) from every element array so the all the elements will be positive.

@spytonic4171

2 жыл бұрын

@@harshitrawat138 truee but the problems comes when there is a random so if we check for negetive numbers at starting and find diff with each number the we can return it other wise we can continue this algo nice idea

@kaushalwaghela429

2 жыл бұрын

understood if possible, please give leetcode and gfg problem links also. thanks :)

@trendtoyou7967

2 жыл бұрын

We need not calculate minimum repeatedly. Traverse last row in dp array in reverse order and return first true cell.... Total-2*i

understood, but the leetcode question mentioned in the sheet requires meet in the middle approach as it has got negative values, and tabulation fails in this case.

@ankitanand1539

8 ай бұрын

Use long long

@fettuccine794

6 ай бұрын

Exactly !!!

@dhananjaygorain6375

4 ай бұрын

@@ankitanand1539 still it showing runtime error can you give your code please

@gamersgame43

3 ай бұрын

use unordered_set?

@ganishk3568

5 күн бұрын

@aryadhjain7893 that is not an issue if you have initial offset of 10⁷. But the problem is requires both the partitions should be of equal size.

bro this problem work only for +ve numbers and not on negative numbers. pls do make a follow up for negative numbers as well, as it might come up in an interview. good companies do ask such. thanks

@user-hz2nh8kg6x

8 ай бұрын

Did you come across a solution for the negative numbers?

@EerieEntertainment-mc4ce

6 ай бұрын

@@user-hz2nh8kg6x agar array ka minimum element negative hai to saare element me use add krke array ko non negative banalo

@manikiran949

5 ай бұрын

Hey did you find a dp solution for negative numbers ? , I have seen in leetcode that it is unsolvable with dp for negative numbers .Thanks

@ramakrishnan4356

4 ай бұрын

Instead of storing in array store the same in map create map where you can store corresponding sum for values this way we can handle negatives also

@safiwasif2905

Ай бұрын

@@ramakrishnan4356 thx mate

Understood it very well Thanks for this amazing series You really are contributing a lot to this community Best DP series in the whole youtube

You made the concept clear easily and smoothly🙌

Able to solve this problem without seeing the video and using concepts learned in past two videos. That's the power of striver's lectures. Thanks!!

@tonyconor681

9 ай бұрын

exactly

@pritimurmu7898

8 ай бұрын

bro how did you solve for negetives

@prashantpal3510

7 ай бұрын

me too

I could do the memoized version on my own, but could never do it the bottom-up way. today, i can say that it's clear. and it was damn simple. just checking the sums my array of size n can produce. amazing insight.

Understood! Striver you are just brilliant. Your explanation and these concepts are blowing my mind off! Damn I got lucky coz i found a teacher like you! Thank you so much!

it took me 50 mins to solve the question without looking the answer it's all because of you the way you teach.. ✨✨✨✨

Was able to solve this in a single go, thank you striver bhaiya, only because of these videos I'm able to develop an intuition in DP problems

For those who are having 49/50 testcase passing on coding ninjas iterate the inner loop upto target/2 and while calculating minimum absolute difference, iterate loop from target/2 to 0 and as soon as you get first true value break the loop (maximum the target value when dp[n-1][target] is true , minimum the absolute difference)

@neelulalchandani7429

16 күн бұрын

thanks this helped.

This is the question which I was eagerly waiting for you to upload since the day you uploaded first DP lecture in this playlist.

you made the concept clear easily and smoothly🙌 : )

Best explanation. understood , hope this channel reaches more people

Dude, really thankful to you man. I solved this question and 95% of the previous questions on my own. the reason is you. your explanation is out of the world. thanx again. hope we meet in person in the near future.

Understood. Very nicely explained the tough problem in an elegant way. Thanks.

How do we do this with negative elements as well?

What if we have negative integers in an array, then this approach won't work ??

understood, i dont know why i was skipping dp, it is easy, (you made it easy to understand this). Thankyou.

kudos striver, you are the reason i got my confidence back , thanku so much , appreciate all the hard work you do , it changes life of thousands .

In case of negative integers, what should we can do ?

@VishalGupta-jh9nz

Жыл бұрын

Just add absolute value of minimum integer to every element

@avicr4727

Жыл бұрын

@@VishalGupta-jh9nz can you provide me the code it will be very helpful

@VishalGupta-jh9nz

Жыл бұрын

@@avicr4727 Yes, I can provide but it gives TLE class Solution { public: int f(int ind, int target, int sum, int size,vector& nums, int n,vector&dp ){ if(ind==-1 && size==n/2){ return abs(target-2*sum); } if(ind==-1 || size>n/2){ return 1e8; } if(dp[sum][size]!=-1)return dp[sum][size]; int notTake = f(ind-1,target,sum,size,nums,n,dp); int take = f(ind-1,target,sum+nums[ind],size+1,nums,n,dp); return dp[sum][size] = min(take,notTake); } int minimumDifference(vector& nums) { int n = nums.size(); int mini = 0; for(int i=0;i

@yogeshlamba5485

Жыл бұрын

@@VishalGupta-jh9nz Consider an array , arr = [-1e7, 4, 7, 1e8, 6] The minimum number here is -1e7, and if go for adding this to all elements, adding it to 1e8 will be out of INT_MAX.

@keshavbaheti7327

Жыл бұрын

​@@yogeshlamba5485 use long long and guess what 1e7 +1e8 is not equal to 1e9.😊

Bhayya can you explain how can we handle the negetive cases where -10^7

Awesome Striver , I was confused in how dp vector is formed step by step and what does it signifies, you cleared it with so much clearity . Respect

@iamnoob7593

5 ай бұрын

same i had doubt too abt it now its clear.

thanks striver,I am able to improve my coding skills the main reason is you and your way of teaching

Striver bhaiya i think it can be further optimized in terms of time and space if we take our sum as sum/2 initially (as we have taken in DP-15), then the TC : N * (k/2) and SC : (k/2) because we are just bothered about S1 till k/2

@takeUforward

2 жыл бұрын

True.. concept clear hone se u urself can do these small things :P

@sparks8754

2 жыл бұрын

Inspiring

@deepaksarvepalli2344

2 жыл бұрын

I am searching for this comment... satisfied...😂

@vanshsehgal9475

2 жыл бұрын

Can you explain a lit bit more? I did not clearly get what are you trying to say..

@abhishekcs5468

Жыл бұрын

@@vanshsehgal9475 You basically try to find target as upperbound of sum/2 and optimize for closest. Here is the memoized solution without space optimization. --------------------------------------------------------------------------------------------------------------------------- int dfs(int ind, int upperBound, vector& nums, vector& dp){ if(ind > nums.size() - 1) return 0; if(dp[ind][upperBound] != -1) return dp[ind][upperBound]; int notTaken = dfs(ind + 1, upperBound, nums, dp); int taken = -1e8; if(nums[ind]

Quick Tip 💡: If you want to solve this using memoization, you need to make sure that you call the recursive function for all possible targets. For example let the sum = 10, so target = 5. Now if you call function for 5 i.e. F(n,5) it may not always fill the complete dp grid. So you have to call all F(n,5) F(n,4) .... F(n,0) to make sure all dp[i][j] are filled. This won't affect the time complexity as if it was previously calculated it won't be calculated again due to memoization. In tabulation we go from 0 -> n, filling all dp[i][j] no matter what, so in that case it all indexes are filled.

@kishorkumarbehera5412

10 ай бұрын

Can you give me the code for reference ?

@user-ie8sy7wo4m

10 ай бұрын

public class Solution { public static int minSubsetSumDifference(int[] arr, int n) { int sum = 0; for(int num : arr) sum += num; int k = sum/2; if(n==1) return arr[0]; if(k==0) return 0; Boolean[][] dp = new Boolean[n][k+1]; for(int i=k; i>=0; i--) find(arr, i, n-1, dp); for(int i=k; i>=0; i--){ if(dp[n-1][i]!=null && dp[n-1][i]) return sum - (2*i); } return -1; } private static boolean find(int[] arr, int k, int i, Boolean[][] dp){ if(k==0) return true; if(i

@user-ie8sy7wo4m

10 ай бұрын

@@kishorkumarbehera5412 added the code

@kishorkumarbehera5412

10 ай бұрын

@@user-ie8sy7wo4m Instead of calling for each target we can call it for sum/2. So when we are picking and not picking we have the sum of the subset, so we can store the difference between the subset sum and the target which is total sum/2, and taking minimum of all subsets. So when returning the final answer we should check if the total sum is even or odd. Accordingly the answer would be 2*ans or 2*ans+1.

@RohitKumar-jd7un

9 ай бұрын

code for this approach bool helper(int ind,int k,vector &arr,vector &dp) { if(k==0) { return true; } if(ind==0) { if(arr[ind]==k) { return true; } else return false; } if(dp[ind][k]!=-1) { return dp[ind][k]; } bool nottake=helper(ind-1,k,arr,dp); bool take=false; if(arr[ind]

Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥

I appreciate the hardwork you putting

We can optimize space complexity here since maximum value a subset can take for minimum absolute difference is total_sum/2 so we can make 2d vector for total_sum/2 instead of total_sum and then iterate last row of vector from last col and the first cell with true will be subset1.

Amazingly explained!. But I had a doubt won't this method fail if we have negative elements in the given array ? Could you explain this too

@amritanand1714

11 ай бұрын

Yeah it's a problem. I think we cannot solve then through this way. There are questions on leetcode with negative values. Anyone please reply if they have any solution for this?

i found this one a bit harder than the previous ones but gave time watching video and doing it by myself and understood it . great work man . n

Understood! Thank you so much for the amazing explanation!!!

In case of negative integers, what should we can do ,vaiya ?

@HarshKumar-ip5nr

11 ай бұрын

substract min(nums.begin(), nums.end()) from each element.

Understood. Sir, You are really making great efforts for students like us. Thank you for teaching us.

understood,able to solve by my own .What I was doing is calling memoization for every subset sum s1 which is giving me TLE. But using tabulation we don't need to call memoization again and again and can solve in one go

Understood bhaiya!! In short we can say that the dp table last row defines whether the target value is possible from given array or not.Then all possible target values are derived from the dp table and we can take min diff among the all abs diff.

Hey bro! Great video and explanation! Just had a small question. How would you approach a similar problem where the sizes of both the partitioned subsets must be equal?

If array elements are negative what should we do?

@denishfuletra7863

Жыл бұрын

let me know if you find ans for negative elements.

Raj bhaiyya, no one could have taught this better than you, Thank you soo much

Absolutely brilliant!!! Thanks a lot

Great video. I simplified the minimum subset difference as follows: int i = totSum / 2; while (!dp[i]) i- -; // will not go out of bounds since i always stops at dp[0] which is always true return (totSum - i) - i;

Amazing! thankyou DSA parasurama striver best teacher ever in my life.

Very Good Explanation. Understood. I think this will be more than enough

This is the same question I was asked in yesterday's interview. I came with recursive and then tried of memoization. After memoization it is giving me TLE, now I am watching this video

@pawanagrawal7653

2 жыл бұрын

in which company..?

@spytonic4171

2 жыл бұрын

do you use recursion??

How would you handle this problem in case the numbers in an array are negative or zero too? The tabulation wouldn't work in such a scenario.

@sherlockholmes1605

2 жыл бұрын

It would right? if we add an extra check to see if the index is going out of bounds for dp[i-1]th row.

@ihsannuruliman3656

2 жыл бұрын

it would work yeah just check of out of bounds.

@SR-we1vl

2 жыл бұрын

Can you please share the code!

@tusharnain6652

2 жыл бұрын

It wont work with negatives, there's a negative number case in leetcode, this solution fails there.

@jigardoshi2852

2 жыл бұрын

Yes agreed, this DP solution will not work when numbers are negative or 0 or for matter if totalSum of all nums is 0.

In the first block of for loops, we don't need to check the target until the total sum. we can check target until totalSum / 2 if total sum even or totalSum/ 2 + 1 if totalSum is odd.

You made this really easy! Thanks

Please make a video regarding neagtive values too 😓. This one understood❤❤

@harshvardhangupta5323

Жыл бұрын

wont it be the same logic?

@sumerrawat6947

Жыл бұрын

@@harshvardhangupta5323 dp cannot store negetive indexes

@surajbaranwal56.

Жыл бұрын

leetcode qn

@rickk3300

Жыл бұрын

I also have this same doubt

This can be alternatively solved, if we can find a subsequence with sum closest to totalSum/2. Correct me if I'm wrong.

@vedanshbhardwaj6548

Жыл бұрын

ya even I did so, but somehow the space optimised solution went wrong

@amitmahato6404

Жыл бұрын

[2,3,7], sum/2=6, closest sum can be 5 or 7

@vedanshbhardwaj6548

Жыл бұрын

@@amitmahato6404 ya but the catch is we will only check till totalSum/2....because if one is say 5, other is bound to be 7 so why check for anything greater than the totalSum/2

@amitmahato6404

Жыл бұрын

@@vedanshbhardwaj6548 yeh, S1=5, SO S2 WILL BE 7, MIN DIFF IS 2

Understood! Thank you Striver

Understood ❤ and thanks for the inspiration by working at 4AM in the morning.

understood i tried earlier i made recursion but wasn't able to make it to dp ,,,,,,,,,thanks for making it easy

How we can make it work if array contains negative elements as well?

@anshumansharma2251

2 жыл бұрын

meet in the middle or binary search

@aryanbharat9749

2 жыл бұрын

@@anshumansharma2251 can you explain why not for negative numbers I mean cant we use Hash Map or something?

understood, thanks for these amazing lectures bhaiya ❤️

Understood man, grt explanation make every hard concept as easy as you can. then there is not something like difficult. 😇

If negative elements are also present in given array then what will be maxSum ?

@sageoustheory1957

Жыл бұрын

did u find the ans ?

This problem is entirely depending upon the total sum of array . What if the total sum of array is negative. Then we cannot create negative size dp array

@balakrishnanr648

Жыл бұрын

in LC its that way

@softwarefoodiee

Жыл бұрын

Sum cannot be negative sunce its mentioned that all the elements are non-negative.

I have solved this question before watching this video only based on the concepts applied in all prev videos. thank you so much

Greatly simplified!! Understood!!!!

Its a suggestion, If you could explain the need of the array as you explained it in this video , in DP-14 video , as I was very confused as to what those T/F represent till end. Now it gets cleared here. I have traced the whole array for that and also that arr[0]

@amartyagupta9922

Жыл бұрын

arr[0]

Understood. I think if we declare dp array of size [n][total sum/2+1] will also work.

@takeUforward

2 жыл бұрын

Yes works

Amaazing explanation! Understood!🤩❤

UNDERSTOOD... ! Thanks striver for the video... :)

Hey striver, I have understood the concept but can we solve it using recursion ?

@sjsjdsbsjjwjs2659

Жыл бұрын

public class Solution { public static int minSubsetSumDifference(int[] nums, int n) { // Write your code here. int sum=0; for(int x:nums) sum+=x; int res=Integer.MAX_VALUE; for(int i=0;i

@prakharsoni7621

Жыл бұрын

Yes by adding this... for(int i=s;i>=0;i--) f(dp,n-1,i,arr); Your dp Array now fill perform the operation now :)

@harisrashid0773

Жыл бұрын

yes we can but will give tle ;

This code now is giving tle with one test case.

@vedantojha766

8 ай бұрын

Yes

Understood Thanks for this amazing series

understood it clearly. Thank you so much

i solved by finding value closer or equal to the half of total sum. but, i feel ur approach is more clear and concise.

@sameerbilla515

2 жыл бұрын

I did same, but cannot memoize it.. can you please tell how can I memoize it

here's my recursive solution class Solution{ public: int ans=1e8; int solve(int i,int arr[],int sum,int curr,int n,vector& dp){ if(i==n){ ans=min(ans,abs(curr-sum)); return ans; } if(sum

@shadab9764

6 ай бұрын

Thanks man!

UNDERSTOOD............Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

@iamnoob7593

5 ай бұрын

man i just dont understand how is he able to do video recording at freakin 4 AM in the morning , Very few match that level of hardwork.

you really make this question a piece of cake

you are amazing teacher!

great solution , thanks striver

Just because of the previous lectures I was able to solve this problem without watching this lecture. Take a bow... Understood ❤

Explained beautifully ♥

Understood 💯💯 Great Explanation.

Understood! Thank you so much!

great idea of using tabulation of subset traget in finding ,minimum difference between sum of subets (crux: just we need is every possible target sum made by at least some subset or not )

Able to solve with just starting hints of 5min.. Thank you striver.. ❣

understood clear as crystal :))

thank you so much for your hard work

"Understood" ....Guess what I coded this problem with a different approach and my score is 100 in this problem of """DP""" ....It's amazing to solve DP ..Thanks bhaiya .... My code here using memoization.. int findans(int a,int t_sum,vector&arr,int i,int &min_v,vector&dp){ if(i

@AmanKumar-fl5ws

2 жыл бұрын

was looking for this !!

Understood, thanks! I had one doubt, why in the space optimised tabulation approach the answer is wrong if we take the last loop from 0 to sum/2 and why is it correct when we take it from 0 to sum ?

understood ..........thanks for doing gret work sir

Awesome Explanation. Understood.

understood sir!! thank you so much!

US :) was trying to solve this question by myself but failed but once you said what dp[i][j] represent I immediately understood everything and solved it.

Very much Intuitive ✨

beautifully explained.

Why cannot I think of such solutions LoL!!!! Amazing Job!!!

Understood, thank you.

We can have only sum/2+1 columns in our DP array. It also worked else it was giving TLE for 1 case. Love this playlist ❤❤

@himansh4812

10 ай бұрын

Yes. Only columns till totalsum/2 is required.

understood sir, thanks for making this so easy.

Understood, sir. Thank you very much.

Understood! Thank you!

Thanks for knowledge, sir!

Understood bhaiys. Thank you so much for your free and amazing content. :)

Amazing Turned a question into a tool

God level explanation and content ❤‍🔥🔥

We need to look at the constraints here because this only works for positive integer array and not when negative numbers are in the array.