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

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

@@samuraijosh1595 same lol

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; } };

same bro ..

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

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

I did the same but got TLE

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

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

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!

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

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

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

That would have been constant time soln

@@nikhil199029 Still O(n)

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

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

It's not randomized!

@@akshaychavan5511 could be random within a certain topic

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

Wohoo same here 🎉

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

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

I have over 15000 connection requests

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

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