Count Number of Nice Subarrays - Leetcode 1248 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
7:46 - Coding Explanation

leetcode 1248

#neetcode #leetcode #python

[umamanikanta]

8:36 I think there is no need for that while loop
while odd > k:
if nums[ l ]%2 == 0:
odd -= 1
l += 1
m = l
Instead, it can be replaced with
if odd > k:
l = m+1
m = l
odd -= 1

The reason is, the conditional check (if odd == k) suceeding the loop (while odd > k) has already found the first odd number position using the inner loop (while not nums[m]%2)
in the previous iteration. So, there is no need to find it again using the (while loop).
Since, 'odd' variable cannot be greater than k before it equals to k. It make sures that we've the position of first odd number in the current window.

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

[nirmalgurjar]

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.

[DebopriyoBasu]

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

[protodimbo]

Thank you sensei for this secret jutsu

[akshayar]

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

[FishAndChips]

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!

[theindiantruth]

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

[reinventingdwheel]

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?

[AnordinaryMan]

Normal sliding window also works here if you do some cheating. class Solution {
public:
int atMostKOdds(vector<int>& 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 nums, int k) {
return atMostKOdds(nums, k) - atMostKOdds(nums, k - 1);
}
};

[selfhelpguy]

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!

[ozzy-frvj]

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

[MP-nyep]

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

[omkarsawant]

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:
# Append subarray from start+1 to i

# Update prefix_counts with current odd_count
if odd_count in prefix_counts:
# 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)

[AlexLucas-bo]

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

[gourabmukherjee]

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

[zyxw_]

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?

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

[M_O-]

I genuinely like your videos. Thx for uploading 👍