Count Subarrays Where Max Element Appears at Least K Times - Leetcode 2962 - Python
Vložit
- čas přidán 27. 07. 2024
- 🚀 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
Hate the subarray problems. So hit or miss!
I dont struggle with all subarray problem. but subarray problems that involve counting/combinatorics are awful lol
@@samuraijosh1595 same lol
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).
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
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;
}
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!
I was praying that you have a video on this and there you go! thank you.
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
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 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.
superb explanation as always, loved it
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 😊
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.
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.
The way u approach to a solution is just🤯🤯
A big fan of your videos. Can you do a video for word pattern II problem. Thanks in advance.
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?
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.
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
Cool! Just solved it man, very nice :) same solution as you
Please give me luck for my interviews!!
You got this king!! 🤴 (or queen 👸)
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!
am now at the level of identifying the sliding window but not being able to find the final result myself 😐
thanks man
great!
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.
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.
Thanks, everyone. Thanks for answering me. I just needed a simple help and none of you guys gave me that. 👌
Leetcode's randomizer is stuck on sliding window?
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
Just saved me from getting stuck on this problem for 1 hr lol
Hey guys, why don't you explain the leetcode contest questions after completing the contest ?
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?
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
I made the same mistake too
even though cnt is not the best variable name the solution is pretty smart
if i would explain to my friend i would like this
You mention it's n^2 sub arrays. Isn't it the arithmetic series ? The number of sub arryas are n(n+1)/2
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.
is this code working?
make a leetcode 100k montage
Solved it! 3 sliding window problems in a row!
Wohoo same here 🎉
I also made that mistake
What about this ? 12:42
for maxCount >= k && start
Some of the subarray problems... ughhh
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
man I waited so long for your video T_T
Edit: please accept my connection request on LinkedIn 🙏
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