Candy distribution problem
Vložit
- čas přidán 2. 12. 2019
- 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/problems/candy/
🟣 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...
Another great explanation, solved one more important problem because of you. Thanks buddy !!
Welcome :)
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]
👍
Your videos have the best explanations! subscribed for sure
Great
Love u and ur explanations brother..u r a life saver
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.
How to think like that?
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.
Thanks for the explanation Surya Sir! You genius Sir!!!!💫
Welcome 🤗
Perfect explanation. Thank you !!!
This man is a legend.
😅
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
great dude , loved the beautiful explanation
Thank You TechDose. You explained this problem very nicely.
Welcome :)
Thanks for uploading this video. Clear explanation. If possible, please make a video on "Egg Dropping Puzzle" and "Coin Change Problem".
Okay sure :)
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
Fantastic explanation thank you.
Great Explanation sir, Thank you
Welcome :)
Nice explanation 👍👍👍
Thank you!!!!
You are the best!
Welcome
thanks for such a doubtless explanation
Welcome
The Best explanation ever
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?
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
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
I did this with sorting ... That solution was easy to come up with
How?
Nice explanation bro and thanks.but total candidate 15=3+2+1+2+3+2+1+2
Thank you. Great explaination
Welcome :)
Yes Great explanation
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;
}
}
}
😅
God level teaching🙏
Thanks
great explanation buddy
Well explanation sir, thanks, keep posting.
Sure 😃
Please also explain the most optimized approach of this problem.
great explanation
Awesome Solution
Very well explained!
Thanks :)
Thanku..you explained so well!!
Welcome :)
perfect explanation
Excellent explanation sir! Can you please also do one video for 621. Task Scheduler? Highly appreciate it!
Will see that .
@@techdose4u Thanks Sir!
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
Nice explaination!!
Thanks :)
Great explanation
Thanks :)
Very nice explanation
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.
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
good explaination
Thanks :)
great🙌
nicely done
Thanks :)
34 also has to get 3 candy's when the rating is same...
Thank You
Can you provide explanation for 0(1) space solution
how to make it with one array?
Thankyou Tech Dose
Welcome :)
Love you bro!!
♥️
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 😅
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.
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
I think it will not for the case of sorted array
where is the code?
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 :)
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.
Nice explanation but answer would be 17.
Is this a problem to be solved from dynamic programming ?
this is a greedy approach.
This problem can also be solved in one pass nd o(1) space.
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;
}
epic!!
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?
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;
}
}
Shashank Naku telusu man
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 😀"
😂
boring