Candy distribution problem

This video contains a very important problem on candy distribution. We need to find the minimum number of candies required for distribution among children. This is a problem from leetcode. The code link is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[techdoseu]

🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: [phone]

[swapnilingle]

My issue with this solution is, it makes sense only after you know the solution.

However, if you don't know the answer and are trying to devise a solution, in no way will it occur to you to check only left child and then only right childs and then merge.

The intuition looking forward does NOT make sense, looking backwards sure it works.

[pinigantikrishnavamsi]

Thank u for providing the Logic . I wrote python code for this problem

n=int(input())
a=[]
for _ in range(n):
a.append(int(input()))
l=[1]*n
r=[1]*n
c=0
for i in range(1, n): #left comparison#
if(a[i-1]<a[i]):
l[i]=l[i-1]+1
for i in range(n-2, -1, -1): #right comparision
if(a[i+1]<a[i]):
r[i]=r[i+1]+1
for i in range(n): #taking maximum in both
c+=max(l[i], r[i])
print(c)

[TechiiEngineer]

hard level problem seems easy level after watching your explanations

[nightmare_]

Another great explanation, solved one more important problem because of you. Thanks buddy !!

[shivalikagupta]

I had tried both the initial ways which you instructed - sorting and larger, smaller. Even I also made an array comparing left, but then I thought right is left uncovered, it is bound to give incorrect answer and this is where i stumped. Actually it was just a little ahead, doing same with right and then max. however it didn't occur in my mind. Nicely explained thanks.

[abhishekbabbar]

you told us how t0 solve the problem....but we want to know how to think the solution...how does it comes to mind that this question has to be done this way?

[roopeshkummara]

can you explain how if 1st case has 6 candies and 2nd case has 8 candies how do we get 8 candies(14:27)?You told we need to get max(left, right)+1, then in that case we need to get 8+1 candies?

[rosonerri-faithful]

Thanks for the explanation Surya Sir! You genius Sir!!!!💫

[nathanjeong]

Your videos have the best explanations! subscribed for sure

[abhicasm]

Can someone explain me why do we need to take the max ?
When moving from right to left, we can update the left array values to be greater than the right side values. But it doesn't seem to work.
It works for this example too that Tech Dose gave, but when I submit it, it gave wrong ans.

The code ->

public int candy(int[] A) {
int n = A.length;
int[] candy = new int[n];
Arrays.fill(candy, 1);
// left check
for(int i = 1; i< n; i++) {
if(A[i] > A[i-1]) candy[i] = candy[i-1] + 1;
}

//right check
for(int i = n-2; i>=0; i--) {
if(A[i] > A[i+1]) candy[i] = candy[i+1] +1;
}

int ans = 0;
for(int num: candy) {
ans+= num;
}

return ans;
}

Please explain me someone.

[rajattalnikar]

Based on your explanation I have written the C++ Solution for the Problem.


class Solution {
public:
int candy(vector<int>& ratings) {
int n=ratings.size();
int L2R[n];
int R2L[n];

for(int i=0;i<n;i++)
L2R[i]=R2L[i]=1;

for(int i=1;i<n;i++)
{
if(ratings[i]>ratings[i-1])
L2R[i]=L2R[i-1]+1;
}


for(int i=n-2;i>=0;i--)
{
if(ratings[i]>ratings[i+1])
R2L[i]=R2L[i+1]+1;
}

int res[n];

for(int i=0;i<n;i++)
{
res[i]=max(L2R[i], R2L[i]);
}
int ans=accumulate(res, res+n, 0);
return ans;
}
};


faster than 98.66% of submissions.

[alfredoosorio]

Actually there is a O(N Log K) solution where K is the number of distinct ratings it was very easy to come up with that solution you just need to save the original indexes and sort by rating, process the ratings starting from the smallest to the largest. However the optimal solution is O(N) runtime and O(1) space.

[bhishmagaming]

great dude, loved the beautiful explanation

[waqaskhan]

hi all i need one suggestion . i find very hard to understnad the leetcode problem then i come here and just undrsntadn the logic and do the code my self i dont copy code from any where i just take help to understand the alogorithm is it normal or i should not do so ?

[ranjith]

Nice explanation bro and thanks.but total candidate 15=3+2+1+2+3+2+1+2

[asishkumar]

can't we do without using another array while R2L and make changes in first L2R array? (just to reduce space complexity)
Great explanation...Thank you!!!

[abhishekjain]

Thank You TechDose. You explained this problem very nicely.

[srilekha]

Thanks for uploading this video. Clear explanation. If possible, please make a video on "Egg Dropping Puzzle" and "Coin Change Problem".

[vaibhavagarwal]

Please also explain the most optimized approach of this problem.