Can it be done using greedy approach?

#1

Suppose if i sort both arrays and then just calculate by subtracting first ones So will it be fine?

#2

yes you can do that
greedy solution is better one

I’ll try my best to explain this to you.
So 1st lets consider a brute force solution.There are M girls with g1,g2…,gm candies and n boys with b1,b2…,bn chocolates. We can simply check all possible assignments of boys to girls. The 1st boy has m girls available, 2nd boy has m-1 girls available and last boy has m - n + 1 girls available. So the total possible assignments are X = m*(m-1)(m-2)…(m-n+1). so whichever of these X assignments has the minimum sum of abs(bi - gj) is our answer.

Now consider the best possible assignment of all boys to N girls will have the following N girls :
gi1, gi2, gi3, … gin. now think to minimize the absolute differences of candies and chocolates of a couple. Which boy will you assign to the girl with the largest amount of candies?

Take an example :
boys : 10, 5, 8, 6, 12
girls : 1, 8, 5, 12, 9, 16, 13
Now let us say I randomly pick 5 girls out of the above 7 girls to pair with 5 boys and they are:
1, 5, 9, 16, 13
Now you have 5 girls and 5 boys. All we need is an assignment that gives minimum sum of abs arrangements for these 5 selected girls.
which boy would you like to pair the girl with 16 candies to? To me it feels intuitive that I will pair her with the boy having 12 candies as abs(16 - 12) = 4 which will lead to a better ans than if I had paired her with someone else. So out of all 5! possible arrangements, the best arrangement will the one in which girl with most candies is paired with boy with most chocolates and so on.

This is just exactly what sorting does in the DP solution.
we first sort the candies and chocolates. if the boy with most candies is assigned to the kth girl(in sorted order) then all other boys will be assigned to girls in the range 1 to k - 1th.

Short explanation : if you had n boys and n girls you will always assign them in order of increasing candies and chocolates otherwise answer will not be minimum.

#3

there is some problem in your code

try out this testcase
1 4 5
1 2 3 4 5
in this case you are trying to pair 1 with 3 and your answer comes 2
but correct ans is 0

i hope you understand your mistake

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.