Frequency of the Most Frequent Element - Sliding Window - Leetcode 1838

[@misoren9645]

If someone wants help with the intuition behind the condition, its basically asking from the current sliding window e.g. [1, 2, 4], how much do you need to convert it in [4, ,4 ,4], you would need 4 (nums[r]) times the window length (r - l + 1) - the sum of the current window. So nums[r]*(r-l+1) - sum, if this is affordable with budget k (nums[r]*(r-l+1) - sum

[@leul1407]

Thanks

[@sahild5953]

@@leul1407Thanks

[@Sam-dk5id]

thanks!

[@abhayzz03]

Great Explanation Thanks!, For All the java users out there, make sure you use "long" for total and res, wherever you are doing right - left + 1, make sure to convert it to right - left + 1L, while returning the res, you can typecast it simply by (int) res. Good Luck.

[@rommeltito123]

Excellent. I never thought I would watch coding videos right after waking up in the morning.

[@Eddie4k]

I find myself in this same morning routine every day now 😆

[@TacticalDoge101]

same here lmao @@Eddie4k

[@marhawk6468]

There used to be a time I was afraid of leetcode. But thanks to you I no longer am

[@NeetCode]

Haha that's awesome.. I'm sometimes still afraid of LC Hards tho 😱

[@husler7424]

@@NeetCode really ??😨😨same here....

[@prathambhardwaj6797]

I wish I could become like you bro, soon enough !!

[@yourlinuxguy]

I gave you the 100th like . 💘

[@marhawk6468]

@@yourlinuxguy are we soulmates 👉👈

[@ducthinh2412]

great video! I just want to mention that for sliding window problem, we (generally) always advance the right pointer, so it's better for the outer loop to be a for loop instead of a while loop. That way you won't have to remember to increment the right pointer at the end.

[@daianabilbao2771]

I love these explanation videos but sometimes I'm like... how did you come up with this solution? I feel I cannot come up with these solutions on my own. :(

[@rishujeetrai5780]

Don't judge your capabilities till you've solved/tried at least a 100 moderate/hard questions

[@ashantinyongo7632]

I’ve come to realize the vast majority people don’t come up with these solutions on their own. It’s implausible, what is more plausible is reading other people’s solutions and developing pattern recognition that helps you solve new problems.

[@rishujeetrai5780]

@@ashantinyongo7632 exactly like when you solve subarray sum problems, you see the first solution then there are over a dozen variation. Same with binary search and other algorithms

[@glorious_purp_123]

or to simplify the inequality, (num[r] * windowlen - total < k).The num[r] * windowlen - total gives number of increments needed to make all the elements in that window and we can keep expanding this window until num[r] * windowlen - total > k.

[@zachyang1041]

I really like how you explain your thinking process like why are we sorting, why are we using sliding window here. Some people just explain the solutions without explaining why we are doing in that way. Thank.

[@TheElementFive]

A little far fetched to expect someone to be able to come up with that formula in an interview

[@minciNashu]

This one is a 'sliding window' problem, there a bunch of other patterns to practice. So you kinda know what patterns to expect.

[@TejaaaaaaReddy]

But one needs to first figure out that it is a sliding window type problem @@minciNashu

[@ttrey743]

@@minciNashu The sliding window approach isn't hard to come up with. It's the formula used for the window bound check. I feel like that conditional check is what most people consider the hard part of the problem.

[@mahesh_kok]

hey @neetcode I admit that after seeing 5 back to back sliding window problem i attempted this problem on my own I was able to find solution to that in my own terms but was unable to make through all the test cases on leetcode i got almost 50 percent right test cases def maxFrequency(self, nums: List[int], k: int) -> int: arr = sorted(nums, reverse=True) diff = [0] max_ele = arr[0] for ele in arr[1:]: diff.append(max_ele - ele) rep = 0 res = 0 for d in diff: if rep + d

[@koubbe]

Recently discovered your channel. Easy to follow explanation, time complexity analysis, code in Python included. What else can we ask for? Please keep doing these videos.

[@AmitSingh-dc2gz]

how do u arrive at that formula? what was ur thought process?

[@RajPatel-qg1mm]

I came accross so many solution videos for this problem but I didn't understand any of those explanations until it yours. You gave the crystal clear explanation.... thank you so much sir..🙏

[@techwills4619]

I first though of doing it with Dynamic programming. Essentially we create a modified array by incrementing a value the original array (as long as k>0) then we get the greatest frequency and recall the function recursively on the modified array. We update the greatest frequency if the recursive call produced a better value. Which results in O(n^k) time and O(n) space

[@shensean1784]

haha

[@rishabhmalviya331]

nums[r] x (windowLen) is basically a hypothetical maximum area you can have with length as nums[r] and breadth as size of the window. Total is the sum of actual areas(each num having breath 1 and length as value of num) in the window. Now we check if hypothetical area - total area is lesser than K(assume K as increasing area of each number by one). If true then we can increase the actual area to be equal to hypothetical one(can only do this by increasing length of each num so that length of each num is equal).

[@antibarcelona2123]

for java users, declare the total variable as long and you're good to go;

[@MGtvMusic]

Thanks mate, The total sum exceeds int limit at some point right?

[@Chirayu19]

We can also do this by creating a frequency map. The approach mentioned in the video can be used but I came up with another appraoch. Create a frequency map. Check the answer for last element (max). Now come to the second last element. New answer would be the old answer - freq of last element + Now we can move the left pointer by (freq of curr element*diff of last and curr element), basically new k

[@ananyagouda8200]

hey can you provide a pseudo code/code for this

[@ZQutui]

please keep up doing these videos, it's extremely helpful.

[@lalitshah9297]

Nice explanation but I guess the main question is how to arrive at this intuition/formula in interview setup? I mean, if I am seeing this question first time in interview setup - I am not sure how will I arrive at this formula.

[@ramansdf]

I've figured out this pattern in 15 mins, and I'm not genius. Solved only 150 problems If you practice more, it's easy to come up with during the interview

[@victoriatfarrell]

You build the intuition by practicing other sliding window problems

[@ersinerdem7285]

in Java, need to declare total as long type. Otherwise fails in the latter long test cases.

[@jabedhasan21]

For some test cases, the total sum will overflow if you are writing the code in Java Or CPP. So int that case use this logic while (nums[r] * (r - l + 1) - total > k)

[@harshilsutariya1793]

but why ?

[@yashwanthsai762]

can u pls explain

[@aniketv2370]

@@yashwanthsai762 because total+k turns out to be a big value which overflows so either typecast it as a long or use this formula

[@adududuke3995]

What if we start the two pointers from the right after sorting. That way we have a max variable that gets updated. So we increase the value at p2 till equals p1 while K is still available. Given ----- 1,2,3,5,7,10 and K = 8, p1 and p2 = 10. p2 moves to 7 ( edge case - if p2 === p2+1, we move p2 again p2-1) and we increase it to 10. K is now left with 5 and Max value is 2. p2 moves to 5 and we can take it to 10. K is now 0 and Max is updated to 3. SInce K is used up, we can now reset p1,p2 to 7, reset K to 8 and repeat

[@ManishR-ov2gz]

I have one doubt the sliding window condition/formula how do you guys come up with it ? I dont think I can ever look at a problem and just figure out a formula like that

[@vaishnavidaber5976]

Such a great explanation. Thank you!

[@anandsardesai301]

not sure how its going to work on input in above example like 1,1,1,2... & k = 2. Its saying that max window size is 3 at index = 2. But not sure how k=2 can be distributed to get that frequency.

[@jonaskhanwald566]

keep posting. never stop

[@priyanshumakwana5034]

Guys please correct me if I am wrong, but if we increment both the values of 1s by 1 each, thus exhausting our budget, won't the answer for the greatest frequency come out as 4 ( [ 1, 2, 2, 2, 2, 4] ) ? Since there will be 4 number of 2s now? How is this logic correct then?

[@stith_pragya]

Thank You So Much for this wonderful video.........................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@ajaymishra1511]

how we can do it with brute force or nested loop + hashing?

[@abishekbaiju1705]

I was not able to come up with that equation. I found the bruteforce way which of course resulted in TLE. Anyway thanks.

[@gauravpoharkar9797]

brute force solution does work its given as hint as well

[@userre85]

n

[@HarshYadav-xe4ff]

Very nice explanation 😀

[@abhishekkumargupta3605]

very good explanation , it's very useful..

[@jonaskhanwald566]

Frequency of the Most Frequent Element similar problems below. If you have time, explain them too. Longest Subarray of 1's After Deleting One Element Constrained Subsequence Sum Number of Substrings Containing All Three Characters Count Number of Nice Subarrays Replace the Substring for Balanced String Max Consecutive Ones III Binary Subarrays With Sum Subarrays with K Different Integers Fruit Into Baskets Shortest Subarray with Sum at Least K Minimum Size Subarray Sum

[@ranjankumarsingh4601]

Good explanation

[@TejaaaaaaReddy]

I guess it is not easy to get this idea in an actual interview.

[@Ynno2]

Do you have any tips for when to stop looking for a solution with a better complexity? I dismissed a bunch of O(n log n) solutions thinking there's probably an O(n) solution, then gave up in frustration and looked at the solutions, only to find O(n log n) is optimal.

[@aryantarafdar443]

Get an idea from the time constraints bro.

[@jonasp4682]

I'm a noob and for some reason I feel like it'd be easier to start with the right pointer at index len - 1, does that make sense?

[@ravisaharan219]

Great Explanation Man!!

[@adityakrishnajaiswal8663]

res=max (res,r-l+1); why this required?

[@ndas9970]

The answer of the example shown is wrong, the output should be 4 not 2 (frequency).but the code works fine.

[@billycheung7095]

Amazing discovery of this sliding window condition

[@vignesh9678]

What a logic!!! Loved it.

[@sahilnegi2789]

I think this que is hard for someone who is doing that que first time .

[@TIENTI0000]

thanks

[@saipramod41]

Awesome explanation. Can you please do text justification leetcode #68 ?

[@ritwik121]

@neetcode can we have a video on text justification ?

[@jonaskhanwald566]

nobody can explain it better than you. when was this problem posted? I think recently it was..

[@manishparab4427]

best explanation... I tried to solve this problem but could not figure out its sliding window

[@manishparab4427]

again forgot..fml

[@tanknandanijagdishbhai9272]

nice explanation..!

[@irvinge4641]

when you got in google, did you ace all questions in the interview with no mistakes?

[@chaitanyakumar8683]

Heyy Can you please tell us how to come up with these kind of formulas

[@awalkingnosebleed]

how to solve this question using hashing?

[@misoren9645]

Nice video, by the way seeing the time execution distribution, theres a peak faster than the time this solution implemented in C++ took. Is it possible that there is a faster solution?

[@AnandKumar-kz3ls]

c++ solution if anyone stuck with integer overflow runtime error in test cases class Solution { public: int maxFrequency(vector& nums, int k) { sort(nums.begin(),nums.end()); int l=0; int r=0; long long curr_sum=0; int max_elements=-1; while(r

[@krish4659]

myan thank you

[@mnekx]

Amazing man. Keep up the good work

[@himanshurathore9816]

at last one testcase failed and only one is remaining bro help it out!!!! testcase no 70

[@VarunSharma-xd8xd]

class Solution { public int maxFrequency(int[] nums, int k) { int total = 0; int L = 0; int R = 0; int res = 0; Arrays.sort(nums); while (R < nums.length) { total += nums[R]; while (nums[R] * (R - L + 1) > total + k) { // Corrected condition total -= nums[L]; L++; } res = Math.max(res, R - L + 1); R++; } return res; } } why this code failing at 71/73 test case

[@prapti2385]

consider the total variable as long

[@abhaypandey2668]

I solved it a bit different way that is without this sum trick (I was not aware of actual solution) but it actually worked for all the test cases in leet code. At test case 50 it throws time limit Exceeded error but I included the same case and run it alone it worked.🤣 class Solution: def maxFrequency(self, nums, k): length = len(nums) count = 1 max_frequency = None nums.sort() if length == 1: return 1 while count k: break i = i + 1 count = similarCount + i return count I know this is not a good solution at all. But is it ok to start the preparation for the google interview? @NeetCode

[@verma_jay]

Thank you

[@martinlabastie.p9940]

7:03 example

[@shantanukumar4081]

Thanks 👍👍👍 Great explanation

[@sarthakyadav9950]

Dude you are just awesome 🔥🔥🔥

[@amandubey5287]

Hi neetcode. I just wanted to say thank you for all these videos. However I have a leetcode hard problem in sliding window of constant length i guess. Question name " Substring with concatenation of all words". this question has been troubling me for a while now. Can you please make a video on this. Thanks

[@PalakKalsi]

Superb!

[@kirtimanmishra8097]

awesome solution...

[@shashankshekhar8186]

best explanation!!

[@irvinge4641]

oh, because r goes to every element being the most frequent candidate

[@gyandeepdigra8461]

for [1,1,1] k = 2 , your solution will give answer 3 , but it should be 2 . Am i wrong somewhere >?

[@roshninagendra1264]

uh yeah...they're all the same number...so max freq is 3

[@samk64]

the prompt says "at most k operations", i.e. up to k operations. that means you can choose to do no operations if that gives you the max possible frequency.

[@atharvakulkarni3007]

Best Explanation No cap

[@syedhabeebuddin101]

Thanks!

[@mitswadas]

Just amazing

[@AryanChaudhary-b3k]

I feel dumb. I could have never come up with this solution on my own.

[@ameynaik1755]

can you please solve this problem. Thanks! 636. Exclusive Time of Functions

[@rohit-ld6fc]

almost impossible to come up with a solution if you have not seen this problem before!

[@_GOUTHAM]

excellent idea man

[@hanyo3629]

Does anyone know why I'm failing the 70th test case when I'm doing this in Java?

[@diyangli9399]

same here

[@shivangb237]

just convert the total to "long" instead of "int"

[@saipraneeth2395]

thanks alot man

[@MrEdgoll]

many thanks!

[@Cpp_For_Life]

Thanks man ❤❤❤

[@hugenerretho9151]

if u can come up w/ this on fly, u r the god even pope cant code like this

[@rohansodha9555]

Thanks a lot :)

[@yassineacherkouk]

I came up whit all the algorithm except the sorting part.

[@rajsuriyang3427]

I don't know why we are multiplying with window length? PS: I watched this video on repeat for an hour to understand it.

[@roshninagendra1264]

because that would give us the total supposing all the elements of that window are that number. this has to be equal to sum + moves. thus expand, as long as product is greater than sum.

[@jatinbhatoya8420]

you are too good

[@thesounds1676]

how did the people actually come up with this solution :(

[@vecstudio]

awesome

[@parthbhatia341]

This is definitely not a medium

[@pisanghangus2]

EUREKA!

[@hetjayeshbhaipatel1075]

wowwwwww

[@pratikgehlot1973]

ahh haa moment

[@ManavChauhan-ze2bi]

Alright But I don't understand what its say 3 4 5 6 7 and k = 6. The above code fails on it. Edit: My bad I thought you could increment or decrement and for so long I've been butting my head on that, turns out the question is so much easier.

[@tusharvatsa5293]

Your videos are very helpful but your voice is irritating af.

[@triscuit5103]

wtf are you talking about? First of all, what a pointless comment, you are clearly an insecure moron, especially when it comes to social interactions. I feel sorry for you and hope you get better. Second of all, his voice is not the least bit irritating at all, I actually sometimes just listen to his videos as I find his way of talking very calming. And lastly, even if he had an irritating voice (which he certainly does not), learn to be thankful for these amazing videos which are available for all of us for free.

[@andreytamelo1183]

Thanks!