Count Subarrays Where Max Element Appears at Least K Times - Leetcode 2962 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/count-s...
0:00 - Read the problem
0:15 - Drawing Explanation
9:56 - Coding Explanation
leetcode 2962
#neetcode #leetcode #python

[@Rahul-pr1zr]

Hate the subarray problems. So hit or miss!

[@samuraijosh1595]

I dont struggle with all subarray problem. but subarray problems that involve counting/combinatorics are awful lol

[@fireman9068]

@@samuraijosh1595 same lol

[@45052so]

I solved this problem by sliding window with another approach. First I count the subarray that the occurrence of the maximum is less than k, and the answer would be total number of subarray minus the result. The code is similar to the problem yesterday, so I personally think it is better to understand (yet in other languages you need to deal with the overflow problem).

[@AkshatMusic-nl7mx]

I wrote this code but still i'm getting error, please help: class Solution { public: long long countSubarrays(vector& nums, int k) { int n=nums.size(); unordered_mapmp; for(int i=0;imax_freq){ max_freq = freq; max_element = ele; } } int l=0; long long ans =0; unordered_mapmp1; for(int r=0;r=k){ mp1[nums[l]]--; l++; } ans+=r-l+1; } long long result = (n*(n+1))/2; result = result-ans; return result; } };

[@kgCode658]

same bro ..

[@kgCode658]

@@AkshatMusic-nl7mx no need of map we just have to find cnt of max element

[@kgCode658]

class Solution: def countSubarrays(self, nums: List[int], k: int) -> int: left,right = 0,0 cnt = 0 ans = 0 maxEle = max(nums) while right < len(nums): if nums[right] == maxEle : cnt +=1 while cnt >= k: if nums[left] == maxEle: cnt -= 1 left += 1 ans = ans + (right-left+1) right += 1 n = len(nums) return n*(n+1)//2 - ans

[@akhlibaratam2118]

I did the same but got TLE

[@nikhilbhutani5277]

3 mins into the video, got the hint to think of all possible subarrays after count == k, that was it, I was able to solve it. The best part about your videos is you explain your thought process!

[@dxlaam004]

I solved the solution without sliding window and used math :)) The Solution used one for and it beat 100 % of users. It was inspired by the brute force algorithm, but instead of having to use a loop to count the number of subarrays when k is satisfied, I came up with a formula to solve the problem. long long countSubarrays(vector& nums, int k) { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int maxValueCurrent = *max_element(nums.begin(), nums.end()); long long count = 0; long long result = 0; vector key(nums.size() + 1, 0); for (int i = 0; i < nums.size(); i++) { if (nums[i] == maxValueCurrent) { count++; key[count] = i; } if (count >= k) { result += key[count - k + 1] + 1; } } return result; }

[@ugola1]

I was praying that you have a video on this and there you go! thank you.

[@Akhillbj]

A suggestion, If the question specifically asks for ATLEAST, that mean K or More than K are also eligible answers, so why cant we do len(array) - rightPointer ! Which gives the same results

[@plsgivemecat]

definitely correct! this was my code: def countSubarrays(self, nums: List[int], k: int) -> int: count = 0 mx = max(nums) i = j = 0 n = len(nums) c_mx = 0 while j < n: if nums[j] == mx: c_mx += 1 while c_mx >= k: count += (n-j) if nums[i] == mx: c_mx -= 1 i += 1 j += 1 return count

[@cassieguo653]

That's what I did! I think this approach is more intuitive!

[@vijethkashyap151]

Hey, can you please explain? I got the intuition for using the left pointer, but somehow can't wrap my head around this. How does n-j give us the count of valid subarrays? ex: in this array [13,2,3,3] , k = 2. When i=0, j=3, n=len(arr)= 5, how does doing n-j give us the count of subarrays. I am super confused!

[@plsgivemecat]

​@@vijethkashyap151 so in the example, [1,3,2,3,3]. i = 0, j = 3. you want the amount of subarrays ending at j which are valid right? maxElement = 3. so at i=0, j =3, we know there's a valid subarray because occurrences of maxElement is = 2 >= k. now, once we've achieved a minimum threshold of atleast k = 2 occurrences of the max element, anything after that in the array will not matter and will still be a valid subarray. therefore, [1,3,2,3] is a valid subarray and so is [1,3,2,3,3]. gives a total of 2. (n-1) (last index) - j + 1(including the current subarray where j is pointing at) = n-j. in this case, thats 5-3 = 2 which is correct! we'll take another example if you want more clarity. say i extend the array as [1,3,2,3,3,1,2,3,1,2]. n = 10. k = 2. i = 0, j = 3. at j = 3, we've attained at least k = 2 occurrences of the maxElement = 3. that means anything after that, will be counted as a valid subarray. n-j = 10-3 = 7. [1,3,2,3], [1,3,2,3,3], [1,3,2,3,3,1], [1,3,2,3,3,1,2], [1,3,2,3,3,1,2,3], [1,3,2,3,3,1,2,3,1], [1,3,2,3,3,1,2,3,1,2] are all valid subarrays and as you can count, there's 7 of them!

[@mkum2141]

@@plsgivemecat I got to a point that was extremely similar to your code but I wasn't able to get the count += (n-j) part (I just had += 1 which is obviously wrong). Can you explain why you are adding the difference between the length and your right pointer?

[@jaatharsh]

superb explanation as always, loved it

[@pradyumnachakraborty3262]

You can actually store the position of the maximum values in an array. Then, calculate the number of these subarrays between 0 to n. Now, for all other indices, if the index before it was a max, then you add prev-1 to the count, or if it was not a max, then you add prev to the count, where prev keeps a track of the number of such subarrays for the previous cases. And return the final count.

[@Versatile_Naveen]

The way u approach to a solution is just🤯🤯

[@capitaoTigelinha]

Cool! Just solved it man, very nice :) same solution as you Please give me luck for my interviews!!

[@NeetCodeIO]

You got this king!! 🤴 (or queen 👸)

[@ecchioni]

Leetcode's randomizer is stuck on sliding window?

[@ap2s2000]

lately it's staying with a topic/theme for a week or so

[@akshaychavan5511]

It's not randomized!

[@ap2s2000]

@@akshaychavan5511 could be random within a certain topic

[@DeathSugar]

it looks kinda complicated to update it by 1. if we update our right pointer and count became exactly k we can say everything to the left will be valid subarray, so total count increases by size - right, so we just add them and start increase left pointer, adding this diff until count become less then k.

[@groznee]

Another approach is to find the indexes of the max value in the nums array. Then you go over each valid window using the list of indexes and choose the possible nums subarrays for that window. Took me an afternoon to do it but if you want to avoid sliding window it's worth it.

[@MangoTroll34]

As many people have already pointed out, the solution provided in this video (and the editorial) calculates the number of subarrays that can be made with the end of each subarray being the rightmost element in the window. Solving this problem by starting with brute force and then moving to sliding window might lead you to calculate the number of subarrays that can be made with the start of each subarray being the leftmost value of the window (all subarrays after k max elements are valid). I think the second mentioned approach is more intuitive, however, it's important to understand both approaches for other problems 😊

[@adnanmurtaza6914]

Made the same misinterpretation as you in the beginning too lol. What would the solution be for that case and would it still be considered a medium question with that twist?

[@markwu1765]

great!

[@dragon_id_]

am now at the level of identifying the sliding window but not being able to find the final result myself 😐 thanks man

[@shwethaks7994]

A big fan of your videos. Can you do a video for word pattern II problem. Thanks in advance.

[@DebopriyoBasu]

I was solving the problem and I had searched Neetcode 2962 even before the video was published, expecting you to already have uploaded a video solution to today's problem. Good to see you're not too far from there. Amazing consistency! Thanks Neetcode!

I solved it with total subarray minus the subarrays that contains lower than k. But I liked your solution. It is more straightforward, especially the 2nd way, since we generally shift left pointer until the condition fails.

[@nikhil199029]

That would have been constant time soln

@@nikhil199029 Still O(n)

[@dcvc619]

Can I see your code please

@@dcvc619 I tried to reply with a link of my leetcode solution but my comments are disappearing. Anyway, I am posting the code here; class Solution { public long countSubarrays(int[] nums, int k) { int max = 0; for (int num : nums) { max = Math.max(max, num); } int left = 0; int right = 0; long subarraysCount = 0; // this holds subarrays that contains at most k-1 max number. int count = 0; while (right < nums.length) { if (nums[right] == max) { count++; } while (count >= k) { //no need to check left

@@dcvc619 I tried to reply you more than 3 times, but my comments are disappearing (It might be the link or the code, I don't know why) If you can write your contact address I can send a link of my leetcode solution

[@sabalog08]

Do you think you can tackle leetcode problem 2781? I feel like I have the solution right using the sliding window but it's still timing out.

[@user-vp5io1so3i]

Just saved me from getting stuck on this problem for 1 hr lol

[@evanilsonp.8183]

Hi. I'm new to programming and I'd like to be a junior developer soon. I'd like to know If I will do leetcode questions in my interviews as a junior or is it for developers with more experience who wanna join FAANG.

[@evanilsonp.8183]

Thanks, everyone. Thanks for answering me. I just needed a simple help and none of you guys gave me that. 👌

[@rohananthwal2527]

even though cnt is not the best variable name the solution is pretty smart

[@yang5843]

I made the same mistake too

[@sudeepbattu5525]

Hey guys, why don't you explain the leetcode contest questions after completing the contest ?

[@staywithmeforever]

3-0 +1 no of elements that is no of sub arrays every time we get an extra count we will do L-0+1 so every time L+1

[@asagiai4965]

I know your solution works but can't we just add another variable for the last count? this variable will only hold count until k so the final answer is count + xcount?

[@staywithmeforever]

if i would explain to my friend i would like this

[@tejascj9906]

You mention it's n^2 sub arrays. Isn't it the arithmetic series ? The number of sub arryas are n(n+1)/2

[@JuanSB827]

cuz he's talking in O(n) terms, he's not referring to the exact amount.

[@tejascj9906]

@@JuanSB827 The no. of subarrays is not a relative component. No of possible subarrays is a concrete number.

[@nirjhardas446]

is this code working?

[@satyamjha68]

Solved it! 3 sliding window problems in a row!

[@kanuppai6336]

Wohoo same here 🎉

[@pastori2672]

make a leetcode 100k montage

[@Maghawry]

What about this ? 12:42 for maxCount >= k && start

[@shashwatsingh9247]

Some of the subarray problems... ughhh

[@logchamption]

Once u find max_c = k no need to check remaining because every number will form the subarray So the logic goes like this ....... m = max(nums) l = 0 d=defaultdict(int) n = len(nums) c = 0 for r in range(n): If nums[r] == m: d[nums[r]] += 1 While d[nums[r]] >= k: Rem = n-r c += rem If nums[l] == m: d[m] -= 1 l += 1 else: l+=1 return c

[@spsc07]

man I waited so long for your video T_T Edit: please accept my connection request on LinkedIn 🙏

[@NeetCodeIO]

I have over 15000 connection requests

[@spsc07]

@@NeetCodeIO probability of my request getting accepted is x>1/15000

[@leeroymlg4692]

@@spsc07 it's < 1/15000 and how would he even know what profile is yours