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

0:00 - Read the problem
3:35 - Drawing Explanation
14:34 - Coding Explanation

leetcode 1838

#sliding #window #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[misoren]

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 <= k) then a frequency can be achieved with an amount equal to the window length. (e.g. 1 + 2 + 4 = 7, 4 + 4 + 4 = 12, you need 5 to convert it, which is within budget).

[marhawk]

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

[rommeltito]

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

[daianabilbao]

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. :(

[abhayzz]

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.

[ducthinh]

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.

[TheElementFive]

A little far fetched to expect someone to be able to come up with that formula in an 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.

[glorious_purp_]

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.

[zachyang]

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.

[antibarcelona]

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

[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 <= k:
rep += d
res += 1
else:
break
return res

this is my solution..our thinking was in right direction but your approach is the most efficient and works on all test day i will try to come as close as i can to you...

[techwills]

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

[RajPatel-qgmm]

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

[AmitSingh-dcgz]

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

[Chirayu]

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

[lalitshah]

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.

[rishabhmalviya]

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

[ZQutui]

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

[ersinerdem]

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