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.
@MadpolygonDEV2 ай бұрын
Another chat gpt coder
@nirmalgurjar81812 ай бұрын
@@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.
@MadpolygonDEV2 ай бұрын
@@nirmalgurjar8181 your responses are very similar to chatgpt
@nirmalgurjar81812 ай бұрын
@@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-nk9ue14 күн бұрын
@@MadpolygonDEV Yup. Very obvious.
@akshayar59932 ай бұрын
Can you please upload videos for weekly and biweekly challenges too?
@protodimbo2 ай бұрын
Thank you sensei for this secret jutsu
@FishAndChips24782 ай бұрын
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!
@DebopriyoBasu2 ай бұрын
can you tell me some more 3 pointer sliding window problems, so that I can practice further on this?
@miteshjain29422 ай бұрын
Q.15 3Sum is a good 3 pointer problem to start with as its similar to 2sum
@sar33882 ай бұрын
@@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.
@AnordinaryMan0072 ай бұрын
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_onion2 ай бұрын
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?
@chomdua13202 ай бұрын
@@immortalized_onion cause number of exactly subarrays of k = number of at most k - at most k-1
@yang58432 ай бұрын
i didn't cheat and got it to work
@nirmalgurjar81812 ай бұрын
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)
@nirmalgurjar81812 ай бұрын
@@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
@prathapreddyp2 ай бұрын
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!
@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.
@chaitanyasharma62702 ай бұрын
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?
@victoriatfarrell6 күн бұрын
There is no point in feeling bad, as it is an impediment to improvement. It's another experience to learn from without judgment
@ozzy-fr7vj2 ай бұрын
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
@theindiantruth4672 ай бұрын
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
@MP-ny3ep2 ай бұрын
Beautiful explanation as always. Thank you so much for daily leetcode
@selfhelpguy55892 ай бұрын
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!
@omkarsawant92672 ай бұрын
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)
@chien-yuyeh93862 ай бұрын
Thanks for sharing!
@innovativesmartlearning96102 ай бұрын
can you please upload videos of leetcode weekly and biweekly also
@vidhishah91542 ай бұрын
Yes, I would request the same.
@mohanedomer90812 ай бұрын
I genuinely like your videos. Thx for uploading 👍
@zyxw_98762 ай бұрын
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?
@user-ry2of3dj2b2 ай бұрын
Another way of doing this is treating evens as 0s and odds as 1s and using the prefix sum and a hashmap.
@johnniewalkerjohnniewalker24592 ай бұрын
for the middle pointer i gave the variable name firstOddOfWindow.Initialized the firstOddOfWindow to -1 in the beginning.
@arjunc14822 ай бұрын
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
@asagiai49652 ай бұрын
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
@saishivamgupta45842 ай бұрын
it is actually exactly k odd numbers ....not more not less ...you can deduce it from the examples in the video too
@asagiai49652 ай бұрын
@@saishivamgupta4584 thanks for the info. then my solution probably gonna work.
@merchantxd2 ай бұрын
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...
@gourabmukherjee21692 ай бұрын
Is this really o(n) time complexity as claimed in video at 7:40 ? Is yes how?
@deathbombs2 ай бұрын
Rasengan sliding window is insane
@bhuvan99562 ай бұрын
This is a much more intuitive using a prefixSum
@nihalbhandary1622 ай бұрын
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.
@janardannn2 ай бұрын
these absolutely cooked me
@sanchitdeepsingh96632 ай бұрын
thanks
@Antinormanisto2 ай бұрын
Can you give me easier qeustions where I can train? I don't understand it
@deathbombs2 ай бұрын
How do you evem invent this sliding window idea... genius
@xhero96422 ай бұрын
Can you share the solution for 1552. Magnetic Force Between Two Balls
@anonanon65962 ай бұрын
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
@zweitekonto96542 ай бұрын
I like to do my sliding window in a single pass.
@Lil.Mushroom2 ай бұрын
I love neet code
@artariooАй бұрын
this was pretty similar to citadel swe oa 2024
@ajaymishra15112 ай бұрын
It is similar 0 and 1 problem
@giovannigonzalez62722 ай бұрын
I'll never pass a technical interview at this rate.
@yang58432 ай бұрын
Sliding window works for this problem too
@JamesBond-mq7pd2 ай бұрын
How it works?
@yang58432 ай бұрын
@@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-mq7pd2 ай бұрын
@@yang5843 hard to undertstand 🤧😭
@debankumarsahu86032 ай бұрын
Those who solved this with hashmap and permutation & combination
@julianelmasry95562 ай бұрын
I need to one tap more problems
@dev98442 ай бұрын
Advanced jutsu lmao
@mohanedomer90812 ай бұрын
forbidden sliding window lol
@Polly101892 ай бұрын
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❤
@krityaan2 ай бұрын
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
@shinewbiez2 ай бұрын
First
@tuandino6990Ай бұрын
3 pointers, for god sake
@mudit73942 ай бұрын
@GeetainSaar2 ай бұрын
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]