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!

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

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

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

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

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

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

[@AmitSingh-dc2gz]

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

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

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

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

[@abhinayrk985]

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.

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

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

[@ZQutui]

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

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

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

[@ersinerdem7285]

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

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

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

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

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

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

[@ravisaharan219]

Great Explanation Man!!

[@abhishekkumargupta3605]

very good explanation , it's very useful..

[@HarshYadav-xe4ff]

Very nice explanation 😀

[@himanshurathore9816]

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

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

[@andreytamelo1183]

Thanks!

[@sarthakyadav9950]

Dude you are just awesome 🔥🔥🔥

[@TejaaaaaaReddy]

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

[@saipramod41]

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

[@ritwik121]

@neetcode can we have a video on text justification ?

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

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

[@mnembachambuya3592]

Amazing man. Keep up the good work

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

[@vignesh9678]

What a logic!!! Loved it.

[@TIENTI0000]

thanks

[@shantanukumar4081]

Thanks 👍👍👍 Great explanation

[@sahilnegi2789]

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

[@saipraneeth2395]

thanks alot man

[@tanknandanijagdishbhai9272]

nice explanation..!

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

[@PalakKalsi]

Superb!

[@jonaskhanwald566]

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

[@kirtimanmishra8097]

awesome solution...

[@_GOUTHAM]

excellent idea man

[@shashankshekhar8186]

best explanation!!

[@billycheung7095]

Amazing discovery of this sliding window condition

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

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

[@Cpp_For_Life]

Thanks man ❤❤❤

[@ndas9970]

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

[@mitswadas]

Just amazing

[@adityakrishnajaiswal8663]

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

[@verma_jay]

Thank you

[@irvinge4641]

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

[@MrEdgoll]

many thanks!

[@awalkingnosebleed]

how to solve this question using hashing?

[@manishparab4427]

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

[@manishparab4427]

again forgot..fml

[@chaitanyakumar8683]

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

[@martinlabastie.p9940]

7:03 example

[@rohansodha9555]

Thanks a lot :)

[@atharvakulkarni3007]

Best Explanation No cap

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

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

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

[@irvinge4641]

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

[@hugenerretho9151]

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

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

[@jatinbhatoya8420]

you are too good

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

[@yassineacherkouk]

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

[@vecstudio]

awesome

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

[@parthbhatia341]

This is definitely not a medium

[@hetjayeshbhaipatel1075]

wowwwwww

[@pisanghangus2]

EUREKA!

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

[@syedhabeebuddin101]

Thanks!