Count Number of Nice Subarrays (K Odd Numbers)

📋

Problem

Imagine you are analyzing a stream of numbers and want to find how many continuous segments contain exactly K odd numbers - like counting special patterns in a data stream.

Given an integer array nums and an integer k, return the number of nice subarrays. A nice subarray is defined as a contiguous subarray that contains exactly k odd numbers.

1 ≤ nums.length ≤ 10^51 ≤ nums[i] ≤ 10^51 ≤ k ≤ nums.length

Edge cases: All elements are even → output should be 0k equals the length of the array → only one subarray possibleArray with alternating odd and even numbers → multiple overlapping subarrays

</>

IDE

def countNiceSubarrays(nums: list[int], k: int) -> int:public int countNiceSubarrays(int[] nums, int k)int countNiceSubarrays(vector<int>& nums, int k)function countNiceSubarrays(nums, k)

def countNiceSubarrays(nums, k):
    # Write your solution here
    pass

class Solution {
    public int countNiceSubarrays(int[] nums, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int countNiceSubarrays(vector<int>& nums, int k) {
    // Write your solution here
    return 0;
}

function countNiceSubarrays(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Fails to count any subarrays due to incorrect initialization or early return.✅ Initialize result counter properly and ensure loops cover all subarrays; do not return early.

Wrong: 1Counts only one subarray when multiple valid subarrays exist (greedy approach).✅ Continue counting all valid subarrays by expanding and contracting sliding window properly.

Wrong: Non-zero for empty inputDoes not handle empty array edge case, causing incorrect output or crash.✅ Add base case to return 0 if input array is empty.

Wrong: Incorrect count when all elements are evenFails to check odd count properly, counting subarrays with zero odd numbers.✅ Verify odd count before incrementing result; only count subarrays with exactly k odd numbers.

Wrong: TLEUses O(n^2) brute force approach on large input.✅ Implement O(n) sliding window or prefix sums approach to count subarrays efficiently.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before moving on.

Think about tricky cases that break greedy or naive counting methods.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,1,2,1,1],"k":3}

Expected2

⏱ Performance - must finish in 2000ms

The subarrays [1,1,2,1] and [1,2,1,1] each contain exactly 3 odd numbers.

💡 Consider using a sliding window to track the count of odd numbers.

💡 Maintain two pointers and count subarrays with exactly k odd numbers.

💡 Use prefix counts of odd numbers to calculate the number of valid subarrays.

Why it failed: Returned incorrect count for canonical example; likely missed counting all subarrays with exactly k odd numbers. Fix by correctly tracking odd counts and counting valid subarrays.

✓ Correctly counts all subarrays with exactly k odd numbers.

t1_02basic

Input{"nums":[2,2,1,2,1,2,1,2],"k":2}

Expected6

⏱ Performance - must finish in 2000ms

Subarrays with exactly 2 odd numbers are counted, including overlapping ones.

💡 Try enumerating subarrays and counting odd numbers to verify.

💡 Use prefix sums or two pointers to optimize counting.

💡 Remember to count all subarrays, including overlapping ones, with exactly k odd numbers.

Why it failed: Incorrect count due to missing overlapping subarrays or incorrect window adjustments. Fix by carefully expanding and contracting window to count all valid subarrays.

✓ Correctly handles overlapping subarrays and counts all valid ones.

t2_01edge

Input{"nums":[],"k":1}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no subarrays, so result is 0.

💡 Check how your code handles empty input arrays.

💡 Ensure no index errors or invalid loops occur with empty input.

💡 Return 0 immediately if array length is 0 or less than k.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a base case to return 0 when nums is empty.

✓ Handles empty input gracefully and returns 0.

t2_02edge

Input{"nums":[1],"k":1}

Expected1

⏱ Performance - must finish in 2000ms

Single element array with one odd number equals one valid subarray.

💡 Test single-element arrays to verify base cases.

💡 Check if your code counts subarrays of length 1 correctly.

💡 Return 1 if the single element is odd and k=1.

Why it failed: Fails to count single-element subarray when it matches k. Fix by handling single-element arrays correctly.

✓ Correctly counts single-element subarrays matching k.

t2_03edge

Input{"nums":[1,3,5,7],"k":4}

Expected1

⏱ Performance - must finish in 2000ms

k equals array length and all elements are odd, so only one subarray possible.

💡 Check behavior when k equals the length of the array.

💡 Ensure code counts the entire array if it has exactly k odd numbers.

💡 Return 1 if the whole array contains exactly k odd numbers.

Why it failed: Misses counting the entire array when k equals length. Fix by including the full array as a valid subarray if it meets criteria.

✓ Correctly counts the entire array when it contains exactly k odd numbers.

t3_01corner

Input{"nums":[1,2,1,2,1,2,1],"k":3}

Expected4

⏱ Performance - must finish in 2000ms

Multiple overlapping subarrays with exactly 3 odd numbers; tests greedy approach failure.

💡 Beware of greedy approaches that stop counting after first valid subarray.

💡 Use prefix sums or two pointers to count all valid subarrays.

💡 Count subarrays by considering all possible start and end indices with exactly k odd numbers.

Why it failed: Greedy approach undercounts by stopping early. Fix by continuing to count all valid subarrays, not just first found.

✓ Correctly counts all overlapping subarrays with exactly k odd numbers.

t3_02corner

Input{"nums":[2,2,2,2,2],"k":1}

Expected0

⏱ Performance - must finish in 2000ms

All elements even, no subarray contains odd numbers; tests zero odd handling.

💡 Check how your code handles arrays with no odd numbers.

💡 Ensure no subarrays are counted if odd count never reaches k.

💡 Return 0 if no subarray contains exactly k odd numbers.

Why it failed: Incorrectly counts subarrays when no odd numbers exist. Fix by verifying odd count before incrementing result.

✓ Correctly returns 0 when no subarray contains k odd numbers.

t3_03corner

Input{"nums":[1,1,1,1,1],"k":2}

Expected4

⏱ Performance - must finish in 2000ms

All odd numbers; tests correct counting of subarrays with exactly k odd numbers in all-odd array.

💡 Consider how to count subarrays with exactly k odd numbers when all are odd.

💡 Use prefix indices of odd numbers to calculate counts efficiently.

💡 Count subarrays by number of ways to choose start and end indices around odd positions.

Why it failed: Fails to count all valid subarrays in all-odd array. Fix by using prefix sums or indices of odd numbers to count correctly.

✓ Correctly counts all subarrays with exactly k odd numbers in all-odd array.

t4_01performance

Input{"nums":[1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2],"k":50}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) or O(n log n) solution must complete within 2 seconds.

💡 Brute force O(n^2) will time out on large inputs.

💡 Use sliding window or prefix sums for O(n) solution.

💡 Avoid nested loops; track odd counts with two pointers.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing O(n) sliding window or prefix sum method.

✓ Efficient O(n) solution passes within time limit.

Practice

1. You are given a binary array and an integer k. You want to find the length of the longest contiguous subarray containing only 1s after flipping at most k zeros to 1s. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window with two pointers maintaining a window that contains at most k zeros

B. Brute force nested loops checking all subarrays and counting zeros each time

C. Dynamic programming with memoization over subarray indices and zero counts

D. Greedy approach flipping zeros as soon as encountered without shrinking window

Solution

1. Step 1: Understand problem constraints

   The problem requires the longest subarray with at most k zeros flipped to ones, which suggests a variable-size window approach.

2. Step 2: Identify suitable algorithm

   Sliding window with two pointers efficiently tracks the window boundaries and zero count, allowing linear time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window with two pointers is the classic optimal approach for this problem [OK]

Hint: Longest subarray with constraints -> sliding window [OK]

Common Mistakes:

• Assuming greedy flipping without window shrink works
• Using DP unnecessarily
• Brute force is too slow

2. You are given an array of positive integers and a target sum. You need to find the length of the smallest contiguous subarray whose sum is at least the target. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Brute force nested loops checking all subarrays

B. Sorting the array and using binary search for subarray sums

C. Dynamic programming with memoization over subarray sums

D. Sliding window with two pointers adjusting window size dynamically

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the minimal length subarray with sum ≥ target, which suggests a variable-size window approach.

2. Step 2: Identify algorithm that adjusts window size efficiently

   Sliding window with two pointers can expand and shrink the window in O(n) time, ensuring minimal length is found without checking all subarrays.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window is known for O(n) minimal subarray sum solutions [OK]

Hint: Minimal subarray sum -> variable-size sliding window [OK]

Common Mistakes:

• Thinking sorting helps with contiguous subarrays
• Assuming DP is needed for minimal length
• Using brute force for optimality

3. Consider the following Python function that counts the number of contiguous subarrays where the product of all elements is less than k. What is the returned value when calling numSubarrayProductLessThanK([10, 5, 2, 6], 100)?

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1.0
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k and left <= right:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count

easy

A. 8

B. 7

C. 9

D. 10

Solution

1. Step 1: Trace product and window boundaries

   Iterate right pointer: - right=0: product=10 <100, count=1 - right=1: product=50 <100, count=1+2=3 - right=2: product=100 ≥100, shrink window: product/=10=10, left=1, count=3+(2-1+1)=5 - right=3: product=10*6=60 <100, count=5+(3-1+1)=8

2. Step 2: Final count

   Total count is 8 valid subarrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count matches expected output 8 [OK]

Hint: Count increments by window size each iteration [OK]

Common Mistakes:

• Off-by-one in count increment
• Not shrinking window correctly

4. What is the time complexity of the optimal sliding window with count matching algorithm for finding all anagrams of p in s, where n = len(s) and m = len(p)?

medium

A. O(n), because the window slides once over s and frequency counts are updated in constant time.

B. O(n * m), because each window requires comparing frequency maps of size m.

C. O(n * 26), because frequency arrays of fixed size 26 are compared at each step.

D. O(n log m), due to sorting substrings during comparison.

Solution

1. Step 1: Identify main loop operations

   The window slides over s once, so O(n) iterations.

2. Step 2: Check frequency updates and comparisons

   Frequency counts are arrays of fixed size 26, updated in O(1) time; matches count updated in O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window with count matching is linear time [OK]

Hint: Fixed alphabet size makes frequency updates O(1) [OK]

Common Mistakes:

• Assuming frequency map comparison is O(m)
• Confusing n*m with n
• Thinking sorting is involved

5. What is the time complexity of the optimal sliding window solution for the fruits problem, given an input array of length n? Assume fruit types are arbitrary integers but the number of distinct fruit types in the window is limited to two.

medium

A. O(n) because each element is visited at most twice by the two pointers

B. O(n log n) due to maintaining the hash map keys in sorted order

C. O(n²) because the inner while loop can run multiple times per outer iteration

D. O(n * k) where k is the number of distinct fruit types in the array

Solution

1. Step 1: Analyze outer and inner loops

   The right pointer moves from 0 to n-1 once; the left pointer only moves forward when shrinking window.

2. Step 2: Each element is added and removed at most once

   Thus total operations are proportional to 2n, which is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window with hashmap is linear time [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Assuming nested loops multiply to n²
• Thinking hashmap operations add log n
• Confusing distinct fruit count with input size