L12. Candy | Slope Approach Intuition Based

[@ankurdas1477]

Correct code of the optimal approach int sum=1, i=1, n=ratings.size(); while(i

[@shreshthkaushik-hu8bz]

Or you can do this, if we want to avoid doing the down++; after the downward trend/slope. Keeps the code more consistent with the upwards trend. Just add the downward_peak to total/sum before incrementing. # Create a variable to get the length of the ratings array # and a variable to keep track of the index we are on. # We will start with an index of 1 since we want to compare # values from one index before (index - 1) index, length_of_ratings = 1, len(ratings) # Create a variable to keep track of the number # of candies we have given to each children # give the first child, one candy number_of_candies = 1 # Iterate through the ratings array till the end while index < length_of_ratings: # Case-1: Where the neighbor child has same rating if ratings[index] == ratings[index - 1]: # As per requirement number-1 in the question # Give them just one candy number_of_candies += 1 index += 1 # Case-2: Where the child has greater rating than its previous neighbor # We create a variable called "upward_peak" to track the highest amount # of candy we gave while Case-2 is true upward_peak = 1 while index < length_of_ratings and ratings[index] > ratings[index - 1]: upward_peak += 1 number_of_candies += upward_peak index += 1 # Case-3: Where the child has smaller rating than its previous neighbor # We create a variable called "downward_peak" to track the highest amount # of candy we gave while Case-3 is true downward_peak = 1 while index < length_of_ratings and ratings[index] < ratings[index - 1]: number_of_candies += downward_peak downward_peak += 1 index += 1 # At this point of the code, it is possible that our "downward_peak" # was greater than the upward_peak, that means we need to add higher of those peaks # and since we already added one part of it in sum, we will add the difference if downward_peak > upward_peak: number_of_candies += (downward_peak - upward_peak) # Return the summation of the candies given return number_of_candies

[@abhimanyuambastha2595]

All the solutions remove the minimum of down and peak from the sum without properly explaining the reason. Only striver's video explains exactly the reason and also how he came to it. This is the stuff that passes you interviews when you understand how to come to the solution. Just everybody copying a solution without understanding, in interviews you will be completely lost as to what to do and why to do. Thank you for the wonderful explanation

[@manthansingh6302]

In the 2nd approach, you also have to update the right's value in else case. Btw amazing explanation, loved the optimized approach.

[@ayaaniqbal3531]

The last approach was mind Blowing .From my own i could not have imagined this approach.Thank you striver for this amazing video😄

[@Hari-xq1qq]

Best video in entire DSA

[@yuvrajbhardawaj2045]

Small correction in O(2N) solution static int minCandy(int n, int ratings[]) { // code here //Brute Force // int left[] = new int[N]; // int right[] = new int[N]; // left[0]=1; //since we start from left the 1st element will be 1 // right[N-1]=1; //since we start from right the right[N-1] is 1 // for(int i=1;iratings[i-1]) // left[i]=left[i-1]+1; // else // left[i]=1; // } // for(int j=N-2;j>=0;j--){ // if(ratings[j]>ratings[j+1]) // right[j]=right[j+1]+1; // else // right[j]=1; // } // int sum=0; // for(int k=0;k=0;i--){ if(ratings[i]>ratings[i+1]) curr=right+1; else curr=1; right=curr; // right is updated outside if else sum+=Math.max(left[i],curr); } return sum; }

[@anshumansingh6316]

we can avoid one variable itself in better solution, instead of assigning curr to right, we can use curr only

[@SibiRanganathL]

bhai the slow intuition just blew my mind

[@apmotivationakashparmar722]

Great Explaination.

[@suhasherle7350]

int candy(vector& ratings) { int n = ratings.size(); int cnt = 0; vector res(n,1); for(int i = 1; i < n; i++){ if(ratings[i] > ratings[i-1]){ res[i] = res[i-1] + 1; } } cnt += res[n-1]; cout ratings[i+1]){ res[i] = max(res[i+1] + 1, res[i]); } cnt += res[i]; } return cnt; } the O(2N) approach

[@Sangi-sj2dy]

Your videos makes my day awesome

[@karthikkrishna1837]

Whats the intuition behind the two way traversal approach. I remember seeing a couple of paranthesis string problems etc also done by this approach but I dont get the logic behind it. How does this work?

[@nagasrikuncharapu3736]

1x feels like 0.5x to me after listening to all of his classes in 2.5x 😆

[@anuragsekhri2315]

Well explained

[@Dsa_kabaap]

Sir please start making videos on strings and stacks

[@AdityaKumar-be7hx]

Using better variable naming for 2nd appraoch class Solution { public: int candy(vector& ratings) { int n=ratings.size(); vector allocation(n, 1); for(int i=1; iratings[i+1]){ allocation[i]=max(allocation[i], allocation[i+1]+1); } } int candy=0; for(int a:allocation){ candy = candy + a; } return candy; } };

[@Bhavnachouhan-tm5yt]

Thank you bhaiya ❤

[@ajayprabhu465]

suprisingly i came up with most optimal approach by myself, but did not come up with naive solution. IDK my intuition is really good nowadays but , implementation sucks and couldnt code it, any suggestions how to improve implementation skills ? (i can understand others solutions easily but cant code it myself even after knowing intution)

[@ayushivishwakarma9101]

same is the case with me if you get a solution to it pls share it.

[@AmandeepSingh-rd6ql]

Same problem

[@RISHABHKUMAR-w5z]

same problem bro

[@SondiPremSmith]

just go by 30min implementation task if do not get the approach see the hints do it for 10 to 20min roughly dude if you still stuck with the problems see the approach practice repeat 🔁........>>>>>> The one who gave up may fail, but the one who loop(tried and failed) will never loose. so never stop every failed problem teach you something learn it evolve .....

[@sushmi6400]

@@ajayprabhu465 hey how many months does it took for you to complete the entire a to z course and how many hours you used to allocate for it

[@shivamthapliyal4818]

striver can you please increase the frequency of uploading videos. It will help the students like me . I appreciate your work a lot. Thankyou

[@prain_lookmax]

Bro can i start this playlist after learning python

[@vrajpatel9259]

@@prain_lookmax yes, you just need to learn basics of python.. the syntax.. that's all.. than as you will follow this playlist you will catch the remaining things.. but in python dsa is not as hard as compared to c++. if you are not in final year than you can do c++ cuz c++ is way better as it will improve your problem solving skills

[@securelyinsaycure]

Thank you Thank you Thank you

[@iamnoob7593]

SUPERB STRIVER SIR.

[@instinct1098]

Slope Approach is amazing

[@AtulRawat-sf2lw]

hello sir i am in going to be in 1st year can i do strivers dsa course from youtube without learning C++ separately as i have done C please reply...

[@doremon81072]

@@AtulRawat-sf2lw you have enough time, first try to learn any programmin language then start striver's dsa it will be easy, else you will stuck in many things. learn the basicof c++ and oops then start striver's sheet. Best wishes

[@AtulRawat-sf2lw]

@@doremon81072 sir striver playlist has some c++ vedio are they enough or separately i should do c++...

[@ravenin9612]

​@@doremon81072Bro I'm in 4th year, I only know basics of Java and no idea on dsa. Can I start now and be able to get a job by the time I complete my final year?

[@ravenin9612]

​@@doremon81072and is this playlist good? But why is there a lot of videos in this playlist???

[@ujjwalverma8663]

class Solution { public int candy(int[] ratings) { int sum = 1; // Initial candy count for the first child int n = ratings.length; // Number of children int i = 1; // Start from the second child while(i < n) { if (ratings[i] == ratings[i - 1]) { sum++; // Equal ratings, give 1 candy i++; continue; } int peak = 1; // Start with 1 candy for the "uphill" sequence while (i < n && ratings[i] > ratings[i - 1]) { peak++; // Increment candy count as ratings increase sum += peak; // Add to total sum i++; } int down = 1; // Start with 1 candy for the "downhill" sequence while (i < n && ratings[i] < ratings[i - 1]) { down++; // Increment candy count as ratings decrease sum += down; // Add to total sum i++; } // Adjust sum if the peak candy count was greater than the downhill candy count if (peak > down) { sum += peak - down; } } return sum; // Return the total number of candies needed } } My this code is giving wrong answer , can anyone help me out Input ratings = [1,0,2] Output 6 Expected 5

[@fazilshafi8083]

class Solution { public int candy(int[] ratings) { int n = ratings.length; if (n == 0) return 0; int sum = 1; // Start with the first child int up = 0, down = 0, peak = 0; for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { up++; down = 0; peak = up; sum += up + 1; // Add candies for the peak } else if (ratings[i] < ratings[i - 1]) { down++; up = 0; sum += down; // Adjust peak if down exceeds the previous up if (down > peak) { sum += 1; } } else { // Reset counters for flat sections up = down = peak = 0; sum += 1; } } return sum; } } // Up and Down Counters: Track the length of increasing (up) and decreasing (down) sequences. // Peak Adjustment: If a down sequence is longer than the preceding up sequence, the peak value is adjusted to ensure the correct number of candies is distributed. // Edge Case Handling: The code includes resets and adjustments to manage cases where ratings are flat or transition between increasing and decreasing sequences.

[@VibavMahendran]

I am encountering the same issue

[@udhavMohata]

Few edge cases are not handled, related to flat case, check above solution by @rishabhkumar2062

[@furqanmajeed6731]

when u are moving downwards the first value that will be added in sum will be 2 in your code just change the order 1) sum+=down 2)down++;

[@neelulalchandani7429]

understoooooooooooooooooooooood

[@aryankumar3018]

Understood

[@thoughtsofkrishna8963]

What is the optimal approach if they asked for the resultant array ???

[@shashankvashishtha4454]

understood

[@shreyxnsh.14]

Optimised bruteforce solution, with just one vector: class Solution { public: int candy(vector& ratings) { vector vec(ratings.size()); vec[0] = 1; for(int i=1;i ratings[i-1]){ vec[i] = vec[i-1] + 1; }else{ vec[i] = 1; } } for(int i=ratings.size()-2;i >= 0; --i){ if(ratings[i] > ratings[i+1]){ vec[i] = max(vec[i+1] + 1, vec[i]); }else{ vec[i] = max(vec[i], 1); } } return accumulate(vec.begin(), vec.end(), 0LL); } };

[@iamnottech8918]

This mic is scary at night 3am

[@mainaksen5064]

15:46

[@THOSHI-cn6hg]

Great

[@tanishqchauhan8053]

please run the code youself at last it shows error many times

[@calisthenics5247]

Can anyone suggest me how to think of intuition by myself? I can only solve medium level problems by my self(not every medium but 30%) but can't solve hard level problems

[@durgeshjadhav01]

[1,0,2] the second approach fails in this test case , not able to submit it on leetcode

[@mahiverma7692]

class Solution { public int candy(int[] ratings) { int n=ratings.length; int[] left=new int[n]; left[0]=1; for(int i=1;iratings[i+1]) cur=right+1; else cur=1; right=cur; sum+=Math.max(cur, left[i]); } return sum; } } It works , hope it helps

[@kinjalkyadav6359]

Amazon interview question!

[@LIGHT2DARKNess1929]

Is there anyone who completed the whole playlist?????

[@storm19019]

Is it patented approach

[@rishabhkumar2062]

Striver i made changes to your code , to include some of the edge cases , this is my code " class Solution { public int candy(int[] arr) { int i =1; int sum =1; int n = arr.length-1; while(i

[@GokulGajapathi]

thanks a lot bro. I got confused and got stuck for 3 days in this problem

[@suryakalyan5286]

It's working... Guess this comment should be pinned.

[@pradeepkumawat1220]

First like 🎉

[@harshalrelan3113]

the 2nd O(2N) doesn't seem to be working.... pls cross check

[@Ajay-cv1zs]

yes the right variable is not updated correctly for else case. Actually u don't need the right variable sum:= max(1,candies[n-1]) cur:=1 //right traversal for i:=n-2;i>=0;i--{ if ratings[i]>ratings[i+1]{ cur++ }else{ cur=1 } sum+=max(candies[i],cur) candies[i] = max(candies[i],cur) }

[@Ajay-cv1zs]

O(2N) solution, actually u dont need right variable. sum:= max(1,candies[n-1]) cur:=1 //right traversal for i:=n-2;i>=0;i--{ if ratings[i]>ratings[i+1]{ cur++ }else{ cur=1 } sum+=max(candies[i],cur) candies[i] = max(candies[i],cur) }

[@storm19019]

?

[@hiteshpatwal9688]

Livestream of weekly and biweekly leetcode needed 🫡✅✅✅or else answers video of each contest please bro 😔😔

[@vigneshs1852]

He also has his life bro..he is working hard for doing this ...there are some small youtubers who are doing those contest answers😊😊😊

[@saimasyeda6544]

Understood