Count Number of Nice Subarrays - Leetcode 1248 - Python

[@jad_c]

these are cooking me

[@nirmalgurjar8181]

3 Pointers is a useful technique for such problems. This time naming pointers as l, m, r is more intuitive. Understanding 3 pointers after 2 pointers expertise will instantly help you pick the technique. Typical 2 pointers template would be: 1: Initialize: l, r = 0 2: Iterate: While( r < len) or for loop from r = 0 to length or untill in bound 3: Update condition: update condition for current r 4: Revalidate condition: Start while(invalid) loop for invalid condition, l++ to shrink window and update condition, this logic can be converted to type 4 (remove while to if) ie. for max len problems , incrementing l and r together 5: Update answer: If condition is still valid then update answer, loop ends. Template remains same with some modification, one who is familiar with this template will instantly pick 3 pointers technique.

[@MadpolygonDEV]

Another chat gpt coder

[@nirmalgurjar8181]

@@MadpolygonDEV Never used chat GPT, its practice and after tons of practice you will observe few templates immerge for some specific type of problems. Remembering such template can yield you save some time, instead thinking what, where and how to write while loop, you only focus on main problem logic. Neetcode said earlier in his one of the videos you need balance between remembering few standard things and thinking fresh and I agree. Its upto you how you want to go. Good Luck.

[@MadpolygonDEV]

@@nirmalgurjar8181 your responses are very similar to chatgpt

[@nirmalgurjar8181]

@@MadpolygonDEV Dont know why, but here is another tip, remember binary search template pattern, upper bound, lower bound, quicksort, mergesort, 2 pointers, few standard algorithm ie. union find, dijkstra, prims, typical BFS, Tries etc, also be standard with naming variables if you want to save time while coding a problem in real interview and instead invest that time in actual problem.

[@FreeDomSy-nk9ue]

@@MadpolygonDEV Yup. Very obvious.

[@binwangcu]

This can be the same as LC560 - subarray sum to K. If you preprocess the array by %2, then "count of odd numbers is k" is equivalent to "sum of remainder is k". In fact, just one additional lime to LC560 solution at the beginning: nums = [n%2 for n in nums]

[@protodimbo]

Thank you sensei for this secret jutsu

[@AnordinaryMan007]

Normal sliding window also works here if you do some cheating. class Solution { public: int atMostKOdds(vector& nums, int k) { int start = 0; int count = 0; int oddCount = 0; for (int end = 0; end < nums.size(); end++) { if (nums[end] % 2 != 0) { oddCount++; } while (oddCount > k) { if (nums[start] % 2 != 0) { oddCount--; } start++; } count += (end - start + 1); } return count; } int numberOfSubarrays(vector& nums, int k) { return atMostKOdds(nums, k) - atMostKOdds(nums, k - 1); } };

[@immortalized_onion]

Why does this work? Find at most k odd subarrays. Then at most k-1 odd sub arrays. How does this deal with the problem of counting the subarrays without shrinking?

[@chomdua1320]

​@@immortalized_onion cause number of exactly subarrays of k = number of at most k - at most k-1

[@yang5843]

i didn't cheat and got it to work

[@nirmalgurjar8181]

This is not cheating, its standard algorithm, we can use this trick, when question asking for exact condition. if asking for k exact which is equal to exact(k) = atmost(k) - atmost(k-1)

[@nirmalgurjar8181]

@@immortalized_onion Because of maths, Exact(k) = Atmost(k) - Atmost(k-1), meaning you find subsets for at most k condition and atmost k - 1 conditions subtracting this will give you exact k. ie. number of subarrays with sum equals to 2 = (num of subarray sum

[@akshayar5993]

Can you please upload videos for weekly and biweekly challenges too?

[@FishAndChips2478]

You are like the avatar, my guy, you came back when I needed you the most, I was struggling hard with this one, gasping for air. I love your content, I'll make sure to buy a subscription to your platform!

[@ozzy-fr7vj]

slight improvement, when "odd > k" then instead of moving the "l" (left pointer) we can move the "m" (middle pointer) to decrease the count of the odd numbers seen, since m is already pointing to the oldest seen odd numbered location, and left is pointing to the location were the subarray count should begin so, we can use "m" instead of "l" to save a few iterations -> class Solution: def numberOfSubarrays(self, nums: List[int], k: int) -> int: l, m, odd, res = 0, 0, 0, 0 for r in range(len(nums)): if nums[r] & 1 == 1: odd += 1 while odd > k: if nums[m] & 1 == 1: odd -= 1 m += 1 l = m if odd == k: while nums[m] & 1 != 1: m += 1 res += m - l + 1 return res

[@prathapreddyp]

When odd count > k instead of loop, the mid can be incremented and left pointer can be shifted to the mid as shown below: def numberOfSubarrays(self, nums: List[int], k: int) -> int: left, current_window_left, odd_count, subarray_count = 0, 0, 0, 0 for end in range(len(nums)): odd_count += nums[end] % 2 # Count odd elements encountered if odd_count > k: # Shrink window if odd count exceeds allowed limit odd_count -= 1 # Decrement for element leaving window current_window_left += 1 # Update starting index of odd element in current window left = current_window_left if odd_count == k: # If current window has exactly 'k' odd elements while nums[current_window_left] % 2 == 0: # Move until first odd element is found current_window_left += 1 subarray_count += (current_window_left - left + 1) # Count subarrays with 'k' odd elements return subarray_count

[@ayushmamgain9040]

yeaaa I was thinking the same!

[@DebopriyoBasu]

can you tell me some more 3 pointer sliding window problems, so that I can practice further on this?

[@miteshjain2942]

Q.15 3Sum is a good 3 pointer problem to start with as its similar to 2sum

[@sar3388]

@@miteshjain2942 But when you go from 2 sum to 3 sum it becomes obvious what you need to do. In this question though, I had no idea I could do something like this.

[@selfhelpguy5589]

I watched 3 different channels including 2 indian ones one of which is popular, and this is the best video which does not make me go back and watch some of the youtuber's other vidoes. Thank you so much!

[@omkarsawant9267]

Technique using Prefix sum and hash map 1)Prefix Sum with a Twist: We count the number of odd numbers encountered so far while iterating through the array. 2)Hash Map to Track Counts: We use a hash map to keep track of the number of times a particular count of odd numbers has been seen. 3)Counting Valid Subarrays: For each new element, if the number of odd numbers so far minus k has been seen before, it means there exists a subarray ending at the current index with exactly k odd numbers. Py code with comments--> def count_nice_subarrays(nums, k): prefix_counts = {} # Dictionary to store counts of prefix sums count = 0 # Initialize count of nice subarrays odd_count = 0 # Initialize count of odd numbers nice_subarrays = [] # List to store the nice subarrays for i, num in enumerate(nums): if num % 2 != 0: # Check if current number is odd odd_count += 1 # Increment odd_count if odd_count - k in prefix_counts: # Check if there exists a prefix with exactly k odd numbers count += len(prefix_counts[odd_count - k]) # Increment count by the number of such prefixes # Retrieve and store the subarrays that contribute to the count start_indices = prefix_counts[odd_count - k] # Get starting indices of subarrays for start in start_indices: nice_subarrays.append(nums[start+1:i+1]) # Append subarray from start+1 to i # Update prefix_counts with current odd_count if odd_count in prefix_counts: prefix_counts[odd_count].append(i) # Append current index to existing list else: prefix_counts[odd_count] = [i] # Initialize new list with current index return count, nice_subarrays # Return count of nice subarrays and the subarrays themselves # Example usage nums = [1, 1, 2, 1, 1] k = 3 total_count, nice_subarrays = count_nice_subarrays(nums, k) print("Total number of nice subarrays:", total_count) print("Nice subarrays:") for subarray in nice_subarrays: print(subarray)

[@theindiantruth467]

I think it would be better to place m=l out of the while loop, because we just need to update it once after the left is at final position

[@adarshanayak8392]

Really liked the way you explain the question before you get to the solution part, and that just helped me to solve this one on leetcode, amazing content like always, Thanks you.

[@MP-ny3ep]

Beautiful explanation as always. Thank you so much for daily leetcode

[@merchantxd]

thats a way lot better solution.. what i did was converted the array to a Binary Array, then it just became the "Subarray Sum Equals K" problem, where the K odd numbers means sum of the odd numbers basically...

[@AlexLucas-b8o]

Another way of doing this is treating evens as 0s and odds as 1s and using the prefix sum and a hashmap.

[@arjunc1482]

I solved like this return goodSubarray(nums,k) - goodSubarray(nums,k-1) where the function rerturns total number of subarrays with odd number of elements upto k

[@bhuvan9956]

This is a much more intuitive using a prefixSum

[@nihalbhandary162]

pre = collections.defaultdict(int) pre[0]=1 presum,res=0,0 for i in nums: if i%2==1: presum+=1 pre[presum]+=1 if presum>=k: res+=pre[presum-k] return res Prefix sum this could be done in O(n) time.

[@chien-yuyeh9386]

Thanks for sharing!

[@johnniewalkerjohnniewalker2459]

for the middle pointer i gave the variable name firstOddOfWindow.Initialized the firstOddOfWindow to -1 in the beginning.

[@mohanedomer9081]

I genuinely like your videos. Thx for uploading 👍

[@asagiai4965]

My answer/idea is below. But I think I have a question about this. The question says "if there are k odd numbers on it" it doesn't say exactly k odd numbers. So does that mean if you have 4 odds even if k is 3. It still counted as a sub array? My answer btw is using two pointers (a,b) Also a counter that counts The idea is one of the pointer keeps going to right until it gets to k odd number. Counter += 1 When it does the other pointer moves one space. Then the process repeats until the first pointer reach the end of the array. There's probably more other/optimized solution, but this is my answer for now

[@saishivamgupta4584]

it is actually exactly k odd numbers ....not more not less ...you can deduce it from the examples in the video too

[@asagiai4965]

@@saishivamgupta4584 thanks for the info. then my solution probably gonna work.

[@chaitanyasharma6270]

i tried todays quetion i got as far as the normal sliding window solution on my own, should i feel bad that i was not able to do it given that i have solved leetcode 992 before?

[@victoriatfarrell]

There is no point in feeling bad, as it is an impediment to improvement. It's another experience to learn from without judgment

[@anonanon6596]

You are overcomplicating this. I think my idea is simpler: First notice that we can replace all even numbers with 0s and all odd with 1s and it does not change the problem. Second: calculate the running sum array; push 0 in the front. Now we have to find all combination of i and j where i

[@zweitekonto9654]

I like to do my sliding window in a single pass.

[@zyxw_9876]

We are following here a patterns If() While() If() And things went well. But when I tried to change If() If() While() Exactly same code , just moved if block from down to up , code got break. Why is this happening, I am not getting it, anyone knows the reason?

[@innovativesmartlearning9610]

can you please upload videos of leetcode weekly and biweekly also

[@vidhishah9154]

Yes, I would request the same.

[@deathbombs]

Rasengan sliding window is insane

[@giovannigonzalez6272]

I'll never pass a technical interview at this rate.

[@gourabmukherjee2169]

Is this really o(n) time complexity as claimed in video at 7:40 ? Is yes how?

[@debankumarsahu8603]

Those who solved this with hashmap and permutation & combination

[@xhero9642]

Can you share the solution for 1552. Magnetic Force Between Two Balls

[@sanchitdeepsingh9663]

thanks

[@janardannn]

these absolutely cooked me

[@deathbombs]

How do you evem invent this sliding window idea... genius

[@yang5843]

Sliding window works for this problem too

[@JamesBond-mq7pd]

How it works?

[@yang5843]

@@JamesBond-mq7pd let's say you want a subarray of 3 odd integers, if your current odd integers is 4, you just need to find if a subarray of 1 odd integers exists

[@JamesBond-mq7pd]

@@yang5843 hard to undertstand 🤧😭

[@Lil.Mushroom]

I love neet code

[@artarioo]

this was pretty similar to citadel swe oa 2024

[@stardust5584]

I cant believe it, in only less than half year the time map from most people over 600ms, to right now the largest number on the x scale is 154ms, I dont know if over 200ms answer will be accepted... WHY?????

[@stardust5584]

Maybe test cases change?

[@Polly10189]

When I saw this Ques I was like this is too easy because I will use Sliding Window... And wondering why it is a Medium difficulty. Thanks❤

[@krityaan]

Please try it without looking up the answers xD You'll see this question takes quite a bit of thought and has varied strategies to solve

[@Antinormanisto]

Can you give me easier qeustions where I can train? I don't understand it

[@ajaymishra1511]

It is similar 0 and 1 problem

[@julianelmasry9556]

I need to one tap more problems

[@dev9844]

Advanced jutsu lmao

[@mohanedomer9081]

forbidden sliding window lol

[@tuandino6990]

3 pointers, for god sake

[@mudit7394]

[@shinewbiez]

First

[@Aditya_6996]

wtf is this question

[@GeetainSaar]

bro are you indian 🍑

[@vuchintsutapalli]

i have used prefix sum. any feedback would be great .accepted /** * @param {number[]} nums * @param {number} k * @return {number} */ var numberOfSubarrays = function (nums, k) { nums = nums.map((n) => n % 2) let i; let count = 0 for (i = 1; i < nums.length; i++) { nums[i] = nums[i - 1] + nums[i] } let left; let right for (right = 0; right < nums.length; right++) { if (nums[right] == k) { count++ left = 0 while (nums[left] == 0) { count++ left++ } } else if (nums[right] > k) { left = 0 let excess = nums[right] - k while (nums[left]

[@bonagiriumamahesh3347]

aey bro in law, correct answer ponnu . mkld