Brute Force approach

Time complexity: O(n²). Space complexity: O(1).

The brute force approach involves checking every possible subarray in the given array to count how many odd numbers are present. If a subarray contains exactly k odd numbers, we count it as a nice subarray.

The time complexity is O(n²) because we are using two nested loops to check all possible subarrays. The space complexity is O(1) since we are using a constant amount of extra space.

1. Step 1: Initialize a counter for nice subarrays.
2. Step 2: Use two nested loops to generate all possible subarrays.
3. Step 3: For each subarray, count the number of odd numbers.
4. Step 4: If the count of odd numbers equals k, increment the counter.
5. Step 5: Return the counter after checking all subarrays.

For nums = [1,1,2,1,1] and k = 3: 1. Subarray [1,1,2,1]: odd_count = 3 (count = 1) 2. Subarray [1,2,1,1]: odd_count = 3 (count = 2) 3. All other subarrays have odd_count < 3.

Optimal Solution approach

Time complexity: Unknown. Space complexity: Unknown.

The optimal approach uses a sliding window technique combined with a prefix sum to efficiently count the number of nice subarrays. This method allows us to find the count of subarrays with exactly k odd numbers by leveraging the count of subarrays with at most k odd numbers.

1. Step 1: Create a helper function to count subarrays with at most k odd numbers.
2. Step 2: Use this helper function to find the count of subarrays with at most k odd numbers and at most k-1 odd numbers.
3. Step 3: The result is the difference between the two counts.

Common Mistakes

• Not handling edge cases where k is larger than the number of odd numbers.
• Confusing the count of subarrays with at most k odd numbers versus exactly k odd numbers.

Interview Tips

• Always clarify the problem statement and constraints before jumping into coding.
• Think about edge cases and test your solution against them.
• Explain your thought process clearly as you code; it shows your understanding.