L12. Candy | Slope Approach Intuition Based

Find problem link, notes under Step 12: takeuforward.o...
Follow me on socials: linktr.ee/take...

[@jay3952]

15:31 "if you don't know it you will not be able to think about it in an interview" best advise ever

[@frand1956]

For those who are facing errors class Solution { public: int candy(vector& ratings) { int n=ratings.size(); int i=1; int sum=1; while(i

[@Nikhil-jd2up]

7 is not being added in the video as down is being incremented after adding it to sum so the loop stops when down=6 is added to sum and then it is incremented to 7

[@VinothiniAnabayan]

i understood it now after a long video, your command only helped me

[@venkatmalviya2421]

Loved the last approach. I have faced various questions where I wanted to utilise the slope insight but was unable to implement. Thanks for giving me this tool.

[@ayaaniqbal3531]

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

[@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.

[@Gamershettyprateek]

function candy(ratings: number[]): number { let n = ratings.length; let leftN = Array(n).fill(1); for(let i = 1; i < n; i++) { if(ratings[i]> ratings[i-1]){ leftN[i] = leftN[i-1] + 1; } else { leftN[i] = 1; } } let sum = Math.max(leftN[n-1],1); let cur = 1; for(let i = n-2; i >=0; i--) { if(ratings[i]> ratings[i+1]){ cur = cur + 1; } else { cur = 1; } sum += Math.max(leftN[i],cur); } return sum; };

[@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

[@_Dream_Dive_]

if (down >= peak) { sum += (down - peak + 1); // Add the difference here, removing the need for `down++`. }

[@rohandevaki4349]

at 13:33 , you missed right =1; at else curr=1 . this approach is simple and intuitive, thankyou

[@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

[@Pw_Unfiltered]

class Solution { public: int candy(vector& arr) { int n = arr.size(); if (n == 1) return 1; int sum = 1; // Start with 1 candy for the first child int up = 0; // Length of the last increasing sequence int down = 0; // Length of the last decreasing sequence int peak = 0; // Peak of the last increasing sequence for (int i = 1; i < n; ++i) { if (arr[i] > arr[i - 1]) { // Upward slope up++; peak = up; // Update peak down = 0; // Reset downward slope sum += up + 1; // Add candies for this child } else if (arr[i] < arr[i - 1]) { // Downward slope down++; up = 0; // Reset upward slope sum += down; // Add candies for downward slope if (down > peak) { // Adjust if downward slope is longer than the peak sum++; } } else { // Flat slope (arr[i] == arr[i - 1]) up = 0; down = 0; peak = 0; sum += 1; // Each child gets at least 1 candy } } return sum; } };

[@Sangi-sj2dy]

Your videos makes my day awesome

[@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

[@SibiRanganathL]

bhai the slow intuition just blew my mind

[@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_8989]

Bro can i start this playlist after learning python

[@vrajpatel9259]

@@prain_8989 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

[@apmotivationakashparmar722]

Great Explaination.

[@Dsa_kabaap]

Sir please start making videos on strings and stacks

[@securelyinsaycure]

Thank you Thank you Thank you

[@nagasrikuncharapu3736]

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

[@TechieClasher]

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]

@@TechieClasher 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

[@Gamershettyprateek]

2nd Approach Code in JS TC - O(2n) SC - O(n) function candy(ratings: number[]): number { let n = ratings.length; let leftN = Array(n).fill(1); for(let i = 1; i < n; i++) { if(ratings[i]> ratings[i-1]){ leftN[i] = leftN[i-1] + 1; } else { leftN[i] = 1; } } let sum = Math.max(leftN[n-1],1); let cur = 1; for(let i = n-2; i >=0; i--) { if(ratings[i]> ratings[i+1]){ cur = cur + 1; } else { cur = 1; } sum += Math.max(leftN[i],cur); } return sum; };

[@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?

[@Bhavnachouhan-tm5yt]

Thank you bhaiya ❤

[@iamnoob7593]

SUPERB STRIVER SIR.

[@studysprintz]

at 6:05 if are just considering left neighbors even then 4 has higher rating than 0 and its still getting equal candies as 0 . how?? can someone explain??

[@thoughtsofkrishna8963]

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

[@anuragsekhri2315]

Well explained

[@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???

[@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; } };

[@neelulalchandani7429]

understoooooooooooooooooooooood

[@storm19019]

Is it patented approach

[@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++;

[@tanishqchauhan8053]

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

[@surendrathakur6567]

java solution class Solution { public int candy(int[] r) { int n = r.length; if (n == 1) return 1; // Only one child, requires 1 candy. int ans = n; // Start with 1 candy for each child. int i = 1; while (i < n) { // Skip equal ratings, as they get 1 candy each. if (r[i] == r[i - 1]) { i++; continue; } // Handle increasing sequence. int peak = 0; // Count additional candies for increasing sequence. while (i < n && r[i] > r[i - 1]) { peak++; ans += peak; i++; } // Handle decreasing sequence. int down = 0; // Count additional candies for decreasing sequence. while (i < n && r[i] < r[i - 1]) { down++; ans += down; i++; } // Adjust for the peak in the valley where increasing and decreasing meet. ans -= Math.min(peak, down); // Avoid double-counting peak. } return ans; } }

[@JaydeepJayswal231]

what if peak elements are multiple, then you are adding only 1 for every other peak element, not the value of peak, please answer if anybody knows

[@kartikdalai7998]

Still by adding only one it will work . As rest will no need to change,

[@ashusingh0079]

how does this code will work for 1,2,3,3,3,3

[@THOSHI-cn6hg]

Great

[@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

[@aryankumar3018]

Understood

[@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) }

[@AKS-l3m]

undersood

[@pradeepkumawat1220]

First like 🎉

[@mainaksen5064]

15:46

[@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.

[@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); } };

[@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

[@luckygarg2294]

Most of the optimal algorithms you can't think yourself, you have to know about them already to catch the intuition, says Striver himself

[@kinjalkyadav6359]

Amazon interview question!

[@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) }

[@LIGHT2DARKNess1929]

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

[@shashankvashishtha4454]

understood

[@storm19019]

?

[@iamnottech8918]

This mic is scary at night 3am

[@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

[@abhinanda7049]

understood

[@fanofabdevillersandmathslo5960]

Understood