Count Number of Nice Subarrays

📋

Problem

Imagine you are analyzing user activity logs and want to find how many time intervals contain exactly k odd events, helping detect patterns of interest.

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 0All elements are odd and k equals array length → output 1k = 1 and array has multiple odd numbers separated by evens → count each single odd subarray

</>

IDE

def count_nice_subarrays(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 count_nice_subarrays(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: 0Not counting any subarrays because prefix sums or hashmap counts are not maintained.✅ Initialize hashmap with {0:1} and update counts of prefix sums at each step; sum counts for prefix_sum - k.

Wrong: 1Counting only one subarray or first occurrence, missing overlapping subarrays.✅ Use hashmap to count frequencies of prefix sums and sum counts for prefix_sum - k to count all valid subarrays.

Wrong: Incorrect large numberOff-by-one error in prefix sums or incorrect hashmap updates causing overcounting.✅ Ensure prefix sums are updated correctly and hashmap counts incremented after checking prefix_sum - k.

Wrong: TLEUsing brute force O(n^2) approach on large inputs.✅ Implement O(n) prefix sum + hashmap counting approach.

✓

Test Cases

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

Review prefix sums and hashmap logic to avoid common counting mistakes.

Optimize your solution to linear time complexity 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.

💡 Count odd numbers in subarrays using prefix sums.

💡 Use a hashmap to track counts of prefix sums of odd counts.

💡 Number of subarrays with k odds = sum of counts of prefix sums with difference k.

Why it failed: Incorrect count likely due to not tracking prefix sums or hashmap counts properly. Fix by maintaining counts of prefix sums of odd counts and summing counts for prefix_sum - k.

✓ Correctly counts subarrays with exactly k odd numbers using prefix sums and hashmap.

t1_02basic

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

Expected4

⏱ Performance - must finish in 2000ms

Subarrays with exactly 2 odd numbers are: [2,2,1,2,1], [2,1,2,1,2], [1,2,1,2,2], [2,1,2,2,1].

💡 Identify odd numbers and track their prefix sums.

💡 Use hashmap to count how many prefix sums differ by k.

💡 Sum counts of prefix sums where current prefix_sum - k exists.

Why it failed: Failing to count all valid subarrays due to missing prefix sum counts or incorrect hashmap updates. Fix by updating hashmap counts after checking for prefix_sum - k.

✓ Correctly identifies all subarrays with exactly k odd numbers.

t2_01edge

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

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no subarrays, so result is 0.

💡 Check behavior when input array is empty.

💡 No subarrays exist if array length is zero.

💡 Return 0 immediately if nums is empty.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a check for empty array and returning 0.

✓ Handles empty input correctly by returning 0.

t2_02edge

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

Expected1

⏱ Performance - must finish in 2000ms

Single element array with one odd number equals k, so one nice subarray.

💡 Test single element arrays.

💡 Check if single element is odd and k=1.

💡 Return 1 if nums[0] is odd and k=1, else 0.

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

✓ Correctly counts single element subarray matching k.

t2_03edge

Input{"nums":[2,4,6,8],"k":2}

Expected0

⏱ Performance - must finish in 2000ms

All elements are even, so no subarray contains any odd numbers, result is 0.

💡 Check arrays with no odd numbers.

💡 No subarray can have k>0 odd numbers if all are even.

💡 Return 0 if total odd count in array is less than k.

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

✓ Correctly returns 0 when no odd numbers exist.

t3_01corner

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

Expected3

⏱ Performance - must finish in 2000ms

Subarrays with exactly 3 odd numbers are: [1,1,1], [1,1,1], [1,1,1] starting at indices 0,1,2 respectively.

💡 Beware of counting overlapping subarrays correctly.

💡 Prefix sums must count all valid subarrays, not just first occurrences.

💡 Use hashmap to count prefix sums frequencies and sum counts for prefix_sum - k.

Why it failed: Greedy approach counting only first k odd numbers misses overlapping subarrays. Fix by using prefix sums and hashmap to count all valid subarrays.

✓ Correctly counts overlapping subarrays with exactly k odd numbers.

t3_02corner

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

Expected4

⏱ Performance - must finish in 2000ms

Subarrays with exactly 2 odd numbers: [1,2,1], [2,1,2,1], [1,2,1,2], [1,2,1,2,1].

💡 Avoid confusing 0/1 knapsack style counting with exact k odd count.

💡 Track prefix sums of odd counts, not just presence of odd numbers.

💡 Count all prefix sums where prefix_sum - k exists.

Why it failed: Confusing 0/1 vs unbounded counting leads to incorrect counts. Fix by counting prefix sums of odd counts and summing counts for prefix_sum - k.

✓ Correctly counts all subarrays with exactly k odd numbers.

t3_03corner

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

Expected6

⏱ Performance - must finish in 2000ms

Multiple subarrays with exactly 2 odd numbers exist, including those separated by even numbers.

💡 Check that even numbers do not disrupt counting of odd numbers.

💡 Prefix sums count odd numbers cumulatively regardless of even numbers.

💡 Use hashmap to count prefix sums and sum counts for prefix_sum - k.

Why it failed: Off-by-one errors in prefix sums cause missed subarrays. Fix by correctly updating prefix sums and hashmap counts at each step.

✓ Correctly counts subarrays with exactly k odd numbers including those separated by evens.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"k":50}

Expected

⏱ Performance - must finish in 2000ms

Input size n=100 with k=50 tests O(n) prefix sum + hashmap solution runs within 2 seconds; brute force O(n^2) will TLE.

💡 Brute force O(n^2) is too slow for n=100.

💡 Use prefix sums and hashmap for O(n) time complexity.

💡 Track counts of prefix sums and sum counts for prefix_sum - k.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing O(n) prefix sum + hashmap counting.

✓ Efficient O(n) solution passes performance test.

Practice

1. Consider the following code snippet for finding the longest contiguous subarray with equal 0s and 1s. What is the value of max_length returned for input [0, 1, 0]?

easy

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace prefix_sum and seen dictionary for each index

   Index 0: num=0 -> prefix_sum=-1, seen={0:-1, -1:0}; Index 1: num=1 -> prefix_sum=0, max_length=1-(-1)=2; Index 2: num=0 -> prefix_sum=-1, max_length=max(2,2-0)=2.

2. Step 2: Return max_length after full iteration

   max_length is 2, corresponding to subarray [0,1] or [1,0].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums correctly track balance; max_length updated only when prefix_sum repeats [OK]

Hint: Track prefix sums and earliest indices carefully [OK]

Common Mistakes:

• Off-by-one in max_length calculation
• Not initializing seen with 0:-1
• Updating max_length incorrectly

2. The following code attempts to find all anagrams of p in s using the sliding window approach. Identify the line that contains a subtle bug causing incorrect results on some inputs.

medium

A. Missing matches adjustment after decreasing s_count[index_l]

B. Line updating s_count[index_l] after removing left char

C. Line appending index l to result when matches == 26

D. Line updating s_count[index_r] and matches after adding right char

Solution

1. Step 1: Identify where matches count is updated

   Matches are updated correctly when adding the right character but not when removing the left character.

2. Step 2: Locate missing matches adjustment

   After decreasing s_count[index_l], matches should be updated if counts now match or mismatch, but this is missing, causing incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug causes false negatives on some inputs due to stale matches count [OK]

Hint: Check matches update after both add and remove steps [OK]

Common Mistakes:

• Forgetting to update matches after removing left char
• Updating matches twice incorrectly
• Off-by-one in window boundaries

3. What is the time complexity of the optimal approach that counts subarrays with maximum bounded by left and right using the subtraction of two counts (countAtMost)?

medium

A. O(n) because it makes two linear passes over the array

B. O(n^2) because it checks all subarrays explicitly

C. O(n log n) due to sorting the array before counting

D. O(n) with O(n) extra space to store intermediate counts

Solution

1. Step 1: Identify operations in countAtMost

   countAtMost iterates over the array once, updating counters in O(1) time per element.

2. Step 2: Analyze overall complexity

   numSubarrayBoundedMax calls countAtMost twice, each O(n), so total time is O(n). No sorting or nested loops involved.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear scans -> O(n) time, constant space [OK]

Hint: Two linear scans, no nested loops or sorting [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming sorting is needed
• Thinking extra space is O(n)

4. What is the time complexity of the optimal prefix sum with hash map solution for the Subarray Sum Equals K problem, given an input array of length n?

medium

A. O(n) because each element is processed once and hash map operations are O(1) on average

B. O(n) for iteration plus O(n) for prefix sum storage, total O(n) space and time

C. O(n log n) due to sorting or balanced tree operations in the hash map

D. O(n^2) due to nested loops over the array

Solution

1. Step 1: Identify main operations

   The algorithm iterates over the array once, updating running_sum and hash map counts.

2. Step 2: Analyze hash map operations

   Hash map insertions and lookups are O(1) on average, so total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No nested loops or sorting involved, so O(n) time complexity. [OK]

Hint: Hash map lookups are average O(1), not O(log n) [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming hash map operations are O(log n)
• Counting prefix sum storage as extra time

5. Suppose the input list to summaryRanges can contain duplicates and is not guaranteed sorted. Which modification ensures correct output with minimal overhead?

hard

A. Sort the input and remove duplicates before applying the two-pointer approach.

B. Use a hash map to count occurrences and then build ranges from keys in arbitrary order.

C. Apply the two-pointer approach directly without sorting, since duplicates don't affect ranges.

D. Use nested loops to check every pair for consecutive sequences, ignoring duplicates.

Solution

1. Step 1: Understand input constraints

   Duplicates and unsorted input break the assumption that consecutive elements are adjacent.

2. Step 2: Modify input to fit algorithm

   Sorting and removing duplicates ensures input is sorted unique, allowing two-pointer approach to work correctly.

3. Step 3: Evaluate other options

   Hash map keys unordered, so ranges can't be built correctly; applying two-pointer without sorting fails; nested loops are inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting + deduplication restores preconditions for linear scan [OK]

Hint: Sort and deduplicate before two-pointer scan [OK]

Common Mistakes:

• Ignoring sorting requirement
• Using hash map keys unordered
• Applying two-pointer on unsorted input