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
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. :(
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.
@@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
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.
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.
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.
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.
@@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.
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.
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
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..🙏
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
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
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).
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.
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
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
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
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)
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.
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?
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
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
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.
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
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
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?
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.
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.
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.
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.
![[DRAGON BALL LEGENDS REVEALS ＆ STUFF] LEGENDS FESTIVAL 2024 Special Edition Part 1](http://i.ytimg.com/vi/mV5bGIswTtQ/mqdefault.jpg)
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
Thanks
@@leul1407Thanks
thanks!
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. :(
Don't judge your capabilities till you've solved/tried at least a 100 moderate/hard questions
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.
@@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
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.
Excellent. I never thought I would watch coding videos right after waking up in the morning.
I find myself in this same morning routine every day now 😆
same here lmao
@@Eddie4k
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.
There used to be a time I was afraid of leetcode. But thanks to you I no longer am
Haha that's awesome.. I'm sometimes still afraid of LC Hards tho 😱
@@NeetCode really ??😨😨same here....
I wish I could become like you bro, soon enough !!
I gave you the 100th like . 💘
@@yourlinuxguy are we soulmates 👉👈
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.
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.
A little far fetched to expect someone to be able to come up with that formula in an interview
This one is a 'sliding window' problem, there a bunch of other patterns to practice. So you kinda know what patterns to expect.
But one needs to first figure out that it is a sliding window type problem @@minciNashu
@@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.
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.
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
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..🙏
how do u arrive at that formula? what was ur thought process?
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
haha
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
hey can you provide a pseudo code/code for this
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).
for java users, declare the total variable as long and you're good to go;
Thanks mate, The total sum exceeds int limit at some point right?
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.
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
You build the intuition by practicing other sliding window problems
in Java, need to declare total as long type. Otherwise fails in the latter long test cases.
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
please keep up doing these videos, it's extremely helpful.
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
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)
but why ?
can u pls explain
@@yashwanthsai762 because total+k turns out to be a big value which overflows so either typecast it as a long or use this formula
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.
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?
keep posting. never stop
Such a great explanation. Thank you!
I was not able to come up with that equation. I found the bruteforce way which of course resulted in TLE. Anyway thanks.
brute force solution does work its given as hint as well
n
I guess it is not easy to get this idea in an actual interview.
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
consider the total variable as long
The answer of the example shown is wrong, the output should be 4 not 2 (frequency).but the code works fine.
at last one testcase failed and only one is remaining bro
help it out!!!!
testcase no 70
I think this que is hard for someone who is doing that que first time .
Thank You So Much for this wonderful video.........................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
how we can do it with brute force or nested loop + hashing?
nobody can explain it better than you. when was this problem posted? I think recently it was..
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
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?
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.
Get an idea from the time constraints bro.
best explanation... I tried to solve this problem but could not figure out its sliding window
again forgot..fml
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
Awesome explanation. Can you please do text justification leetcode #68 ?
@neetcode can we have a video on text justification ?
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
very good explanation , it's very useful..
Very nice explanation 😀
oh, because r goes to every element being the most frequent candidate
when you got in google, did you ace all questions in the interview with no mistakes?
Great Explanation Man!!
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?
res=max (res,r-l+1); why this required?
Amazing discovery of this sliding window condition
for [1,1,1] k = 2 , your solution will give answer 3 , but it should be 2 . Am i wrong somewhere >?
uh yeah...they're all the same number...so max freq is 3
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.
almost impossible to come up with a solution if you have not seen this problem before!
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
myan thank you
Heyy
Can you please tell us how to come up with these kind of formulas
can you please solve this problem. Thanks!
636. Exclusive Time of Functions
What a logic!!! Loved it.
Good explanation
Amazing man. Keep up the good work
I feel dumb. I could have never come up with this solution on my own.
how to solve this question using hashing?
Does anyone know why I'm failing the 70th test case when I'm doing this in Java?
same here
just convert the total to "long" instead of "int"
nice explanation..!
Dude you are just awesome 🔥🔥🔥
Thanks 👍👍👍
Great explanation
7:03 example
I don't know why we are multiplying with window length?
PS: I watched this video on repeat for an hour to understand it.
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.
best explanation!!
excellent idea man
if u can come up w/ this on fly, u r the god even pope cant code like this
awesome solution...
thanks
how did the people actually come up with this solution :(
I came up whit all the algorithm except the sorting part.
Best Explanation No cap
Thanks man ❤❤❤
thanks alot man
Thank you
Superb!
Thanks!
many thanks!
Thanks a lot :)
Just amazing
you are too good
This is definitely not a medium
awesome
EUREKA!
wowwwwww
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.
ahh haa moment
Your videos are very helpful but your voice is irritating af.
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.
Thanks!