Candy distribution problem
Вставка
- Опубліковано 10 лют 2025
- 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 :)
CODE LINK: leetcode.com/p...
🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: +91 8918633037
🔴 𝐂𝐡𝐞𝐜𝐤𝐨𝐮𝐭 𝐚𝐥𝐥 𝐨𝐮𝐫 𝐂𝐨𝐮𝐫𝐬𝐞𝐬: techdose.co.in/
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.
totally agree. I always try to come up to the solution or atleast as closest to it as possible. But qustns like this are very difficult to come up with intutuion.
1,2,88,88,88,2,1 if you check for these tests case
You just need to practice more and more questions to come up with these kinds of approaches. I came up with this same approach on my own.
Ye badi achi baat ki aap ne. :)
True he dont know solution.
hard level problem seems easy level after watching your explanations
🤗
Because it is not the most optimized solution. There is O(n) time and O(1) space solution as well.
Indeed...
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]
👍
Another great explanation, solved one more important problem because of you. Thanks buddy !!
Welcome :)
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.
no problem shivalika ! you seem to be a good girl, it happens sometimes.
This man is a legend.
😅
Thanks for the explanation Surya Sir! You genius Sir!!!!💫
Welcome 🤗
Your videos have the best explanations! subscribed for sure
Great
great dude , loved the beautiful explanation
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.
Nice explanation 👍👍👍
Well explanation sir, thanks, keep posting.
Sure 😃
Yes Great explanation
Perfect explanation. Thank you !!!
Thank You TechDose. You explained this problem very nicely.
Welcome :)
Brother, your videos are great. Can you please let me know what software are you using for creating videos (screen record and drawing on screen)?
Thanks
Nice explanation bro and thanks.but total candidate 15=3+2+1+2+3+2+1+2
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!!!
yes we can broter
Thank you!!!!
You are the best!
Welcome
The Best explanation ever
Love u and ur explanations brother..u r a life saver
Based on your explanation I have written the C++ Solution for the Problem.
class Solution {
public:
int candy(vector& ratings) {
int n=ratings.size();
int L2R[n];
int R2L[n];
for(int i=0;i=0;i--)
{
if(ratings[i]>ratings[i+1])
R2L[i]=R2L[i+1]+1;
}
int res[n];
for(int i=0;i
do not believe leetcode on this rating
Thanks for uploading this video. Clear explanation. If possible, please make a video on "Egg Dropping Puzzle" and "Coin Change Problem".
Okay sure :)
Great Explanation sir, Thank you
Welcome :)
I realised that ascending and descending order cases can be solved without using the Math MAX method, We don't need to do anything on the left2right side loop but on the right2left we can instead use a simple check to max value if else I say!.
Something like below😅
// right 2 left side loop
for(int i= ratings.length - 2; i >= 0; i--){ // {1,3,4,5,2};
if(ratings[i] > ratings[i + 1]){
if(minCandyRatings[i] > minCandyRatings[i + 1]){
continue;
}else{
minCandyRatings[i] = minCandyRatings[i + 1] + 1;
}
}
}
😅
great explanation buddy
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?
it only comes with practice bro !
Keep praticing on such tags where u feel it difficult
Yes you are correct. Do a lot of practice and things will start appearing before you just seeing the question ;)
Thanks 😊
What tags are for this problem ?
@@ajitkumarsingh871 greedy
Please also explain the most optimized approach of this problem.
I did this with sorting ... That solution was easy to come up with
How?
God level teaching🙏
Thanks
Fantastic explanation thank you.
Very nice explanation
Thanks
Awesome Solution
thanks for such a doubtless explanation
Welcome
Very well explained!
Thanks :)
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?
Love you bro!!
♥️
Thank you. Great explaination
Welcome :)
perfect explanation
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.
try using different arrays for right and left check
great🙌
Here is the Python code
class Solution:
def candy(self, ratings: List[int]) -> int:
left_list=[1 for i in range(len(ratings))]
right_list=[1 for i in range(len(ratings))]
for i in range(1,len(ratings)):
if ratings[i]>ratings[i-1]:
left_list[i]=left_list[i-1]+1
for i in range(len(ratings)-2,-1,-1):
if ratings[i]>ratings[i+1]:
right_list[i]=right_list[i+1]+1
total=0
for i in range(len(ratings)):
total+=max(left_list[i],right_list[i])
return total
Thanku..you explained so well!!
Welcome :)
34 also has to get 3 candy's when the rating is same...
Excellent explanation sir! Can you please also do one video for 621. Task Scheduler? Highly appreciate it!
Will see that .
@@techdose4u Thanks Sir!
Nice explaination!!
Thanks :)
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 ?
How to think like that?
How to solve these type of problem
You are given N red pieces of candy and M blue pieces of candy. Write a program to find the number of arrangements of candy in which not more than K pieces of the same color are placed next to each other
Great explanation
Thanks :)
good explaination
Thanks :)
Do you use tab to create these videos or touch screen laptop.
Tab
@@techdose4u thanks for the reply, just wondering how do you move the cursor on the tab, is it some app?
BTW I am a fan of your contents.. you have one of the best explanations videos on Ds & Algo.
Can you provide explanation for 0(1) space solution
Thanks for the explanation, But few of the test cases are yet not cleared in Hacker rank, Can you please suggest any edit
Did you try this on leetcode as well ? I think there might be a little variation somewhere (even possibly on constraints). Please compare with leetcode version.
@@techdose4u Thank You.. i was not including the extreme elemets while scanning right to left.. All cool now. Thanks
@@RahulSharma-cp1dn nice :)
Thankyou Tech Dose
Welcome :)
If we take 12 4 3
Then we need only 3 candies
And with this solution we need 6 candies???
We need 6 candies. 1 candy is guaranteed for everyone. After that, 4 is a nbr of 3 and greater than 3. So, 4 should have atleast 1 candy greater than 3. So, at 4, we will have 2 candies. After that since 12 is adjacent to 4 and greater than 4, therefore, 12 should have atleast 1 candy greater than 4. So, it has 3 candies (2+1). So, total candies reqd = 6. I hope you should concentrate on problem statement 😅
nicely done
Thanks :)
I don't get the max(left, right) concept.
Because of calculation dependency on neighbours.
Here is another way to look at it. If we take min or just the first value or the second value etc, then it might satisfy *only one condition* (that is left neighbor or right neighbor) depending on circumstances.
However if we take max, we are *100% sure* that it will guarantee both neighbor conditions.
I think it will not for the case of sorted array
Nice explanation but answer would be 17.
Thank You
can we do it in single pass through the array?
I dint try. The only important thing to kkow is info about left and right traversal. Then it can be done. Try it.
check the leetcode solution editorial, it can be done with single array therefore it has O(n) space.
And there is an even better solution( which takes no space at all) which uses some slope formula etc, but I didn't understand their leetcode's explanation.
how to make it with one array?
This problem can also be solved in one pass nd o(1) space.
Is this a problem to be solved from dynamic programming ?
this is a greedy approach.
Java Solution accordiung to the explanation
public class Solution {
public int candy(int[] A) {
int [] prefixSum = new int [A.length];
prefixSum[0] =1;
for(int i =1; i< A.length; i++){
if(A[i] > A[i-1]){
prefixSum[i] = prefixSum[i-1] +1;
}
else prefixSum[i] =1;
}
int [] suffixSum = new int [A.length];
suffixSum[A.length -1] =1;
for(int i =A.length -2; i>=0 ; i--){
if(A[i] > A[i+1]){
suffixSum[i] = suffixSum[i+1] +1;
}
else suffixSum[i] =1;
}
int ans =0;
for(int i=0; i< A.length; i++){
ans += Math.max(prefixSum[i], suffixSum[i]);
}
return ans;
}
}
where is the code?
Can you give us the code sir...im getting runtime error
I don't have the code now. I cleaned my setup long back and used different account on leetcode which is closed now 😅 Please see the solution from discussions.
@@techdose4uit's ok thanks sir
Welcome :)
int Solution::candy(vector &A) {
int n = A.size();
vector left(n,1);
vector right(n,1);
for(int i = 0; iA[i+1]){
right[i] = right[i+1]+1;
}
}
int ans = 0;
for(int i = 0; i< n; i++){
ans += max(left[i],right[i]);
}
return ans;
}
How does this make sense? What is the proof of concept? How does it show that minimum number of candies needed with all possible order of combination?
epic!!
For the love of God Ćlement stop I can't I even memorize the dialogues your gf says "do you wanna be SDE at Google 😀"
😂
Shashank Naku telusu man
boring
great explanation