Count Number of Nice Subarrays

Introduction

• Focus of the lecture: Solving problems related to counting subarrays with certain properties— specifically, subarrays with a specified number of odd numbers (termed as 'Nice Subarrays').
• Example problem: Given an array of integers nums and an integer k, find the number of contiguous subarrays that contain exactly k odd numbers.

Explanation of the Problem

• A 'Nice' subarray is defined as one that contains exactly k odd numbers.
• Task: Count the number of such 'Nice' subarrays in the given array nums.

Approach Ideas

1. Basic Understanding and Example Walkthrough

   • Example Array: [7, 1, 2, 3, 5] and k=3
   • Identify subarrays: (e.g., [7, 1, 2] and [1, 2, 3] for k=3)
   • Key insight: Monitor the count of odd numbers within a sliding window.

2. Detailed Algorithm Explanation

   • Initialize pointers (i and j) and count variables.
   • Use a sliding window approach:
     • Expand the window by moving the j pointer until k odd numbers are found.
     • Once found, shrink the window by moving the i pointer until the window is no longer 'Nice'.
   • Use maps/dictionaries to store the count of previously seen odd counts for quick look-ups.

3. Handling Edge Cases/Corners

   • How to handle the inclusion of even numbers: Use a map to recall previous odd counts accurately.
   • Example case handling and running a dry-run
   • Synchronize sliding window approach with map updates.

Coding Details

Approach 1: Using Hash Map

int numberOfSubarrays(vector<int>& nums, int k) {
    unordered_map<int, int> countMap;
    int count = 0, oddCount = 0;
    countMap[0] = 1;
    
    for (int num : nums) {
        oddCount += num % 2;
        count += countMap[oddCount - k];
        countMap[oddCount]++;
    }
    
    return count;
}

• Use a hashmap to store the frequency of odd counts seen so far.
• Iterate over the array, updating the hashmap and checking if the required subarray exists using the hashmap.
• Time Complexity: O(n)
• Space Complexity: O(n)

Approach 2: Sliding Window Improvement

int numberOfSubarrays(vector<int>& nums, int k) {
    int i = 0, j = 0, count = 0, oddCount = 0, validSubarrayCount = 0;
    while (j < nums.size()) {
        if (nums[j] % 2 != 0) oddCount++;
        while (oddCount > k) {
            if (nums[i] % 2 != 0) oddCount--;
            i++;
        }
        validSubarrayCount = 0;
        int temp = i;
        while (oddCount == k) {
            validSubarrayCount++;
            if (nums[temp] % 2 != 0) break;
            temp++;
        }
        count += validSubarrayCount;
        j++;
    }
    return count;
}

• Implement a sliding window to maintain and adjust the count of odd numbers.
• Keep track of valid subarrays formed as you slide the window across the array.
• More space-efficient compared to the hashmap method, but logic increases slightly.

Conclusion

• Emphasized understanding of Nice subarrays using step-by-step code implementation.
• Sloved problem using both hashmap and sliding window techniques.
• Encouraged further exploration of data structures to improve algorithms.