Hate the subarray problems. So hit or miss!

@samuraijosh1595

3 ай бұрын

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

@fireman9068

3 ай бұрын

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

@AkshatMusic-nl7mx

3 ай бұрын

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

3 ай бұрын

same bro ..

@kgCode658

3 ай бұрын

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

@kgCode658

3 ай бұрын

class Solution: def countSubarrays(self, nums: List[int], k: int) -> int: left,right = 0,0 cnt = 0 ans = 0 maxEle = max(nums) while right 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

3 ай бұрын

I did the same but got TLE

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 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 { if (nums[i] == maxValueCurrent) { count++; key[count] = i; } if (count >= k) { result += key[count - k + 1] + 1; } } return result; }

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

superb explanation as always, loved it

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

3 ай бұрын

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

3 ай бұрын

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

@vijethkashyap151

3 ай бұрын

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

3 ай бұрын

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

3 ай бұрын

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

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.

The way u approach to a solution is just🤯🤯

great!

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 😊

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

@NeetCodeIO

3 ай бұрын

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

Leetcode's randomizer is stuck on sliding window?

@ap2s2000

3 ай бұрын

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

@akshaychavan5511

3 ай бұрын

It's not randomized!

@ap2s2000

3 ай бұрын

@@akshaychavan5511 could be random within a certain topic

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?

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.

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

3 ай бұрын

That would have been constant time soln

@furkanozbay

3 ай бұрын

@@nikhil199029 Still O(n)

@dcvc619

3 ай бұрын

Can I see your code please

@furkanozbay

3 ай бұрын

@@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 if (nums[right] == max) { count++; } while (count >= k) { //no need to check left

@furkanozbay

3 ай бұрын

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

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

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.

@evanilsonp.8183

3 ай бұрын

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

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

I made the same mistake too

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

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

if i would explain to my friend i would like this

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?

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

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

3 ай бұрын

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

@tejascj9906

3 ай бұрын

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

is this code working?

Solved it! 3 sliding window problems in a row!

@kanuppai6336

3 ай бұрын

Wohoo same here 🎉

make a leetcode 100k montage

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

I also made that mistake

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 🙏

@NeetCodeIO

3 ай бұрын

I have over 15000 connection requests

@spsc07

3 ай бұрын

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

@leeroymlg4692

3 ай бұрын

@@spsc07 it's and how would he even know what profile is yours