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. You are given an array of positive integers and a target value x. You want to remove elements from the start and/or end of the array so that the sum of removed elements equals x. Which approach guarantees finding the minimum number of removals efficiently?

easy

A. Use a greedy approach removing the largest elements first from either end until sum equals x.

B. Find the longest subarray whose sum equals total sum minus x using a sliding window, then subtract its length from the array length.

C. Use dynamic programming to find all combinations of prefix and suffix sums that add up to x.

D. Try all possible combinations of removing elements from the start and end using nested loops.

Solution

1. Step 1: Understand the problem transformation

   The problem of removing elements from the ends summing to x is equivalent to finding a subarray in the middle with sum = totalSum - x.

2. Step 2: Recognize the sliding window pattern

   Finding the longest subarray with sum = target (totalSum - x) can be done in O(n) using a sliding window, which leads to minimum removals = array length - longest subarray length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window finds longest subarray efficiently [OK]

Hint: Transform to longest subarray sum problem [OK]

Common Mistakes:

• Trying greedy removal from ends fails on some cases
• Brute force is too slow for large inputs
• Dynamic programming overcomplicates the problem

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

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace prefix sums and first_occurrence updates.

   For input [0,1,0,1], prefix sums are: -1, 0, -1, 0 with offset indexing.

2. Step 2: Update max_length when prefix sum repeats.

   At i=1, prefix_sum=0 repeats at index -1 -> length=2; at i=3, prefix_sum=0 repeats again -> length=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Longest balanced subarray is entire array length 4 [OK]

Hint: Prefix sum repeats indicate balanced subarray [OK]

Common Mistakes:

• Off-by-one in length calculation
• Confusing prefix sum indexing
• Ignoring initial prefix sum at -1

3. The following code attempts to find the pivot index but contains a subtle bug. Which line contains the bug?

def pivotIndex(nums):
    total = sum(nums)
    left_sum = 0
    for i, num in enumerate(nums):
        if left_sum == total - left_sum:
            return i
        left_sum += num
    return -1

medium

A. Line 6: left_sum += num

B. Line 4: for i, num in enumerate(nums):

C. Line 2: total = sum(nums)

D. Line 5: if left_sum == total - left_sum:

Solution

1. Step 1: Understand the condition

   The condition should check if left_sum equals right sum, which is total - left_sum - current num.

2. Step 2: Identify the bug

   The code incorrectly checks if left_sum == total - left_sum, missing subtracting the current num, causing wrong pivot detection.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct condition is left_sum == total - left_sum - num [OK]

Hint: Check if right sum calculation includes current element [OK]

Common Mistakes:

• Forgetting to subtract current num from total
• Misplacing sum updates
• Returning null instead of -1

4. What is the time complexity of the optimal dynamic programming solution that uses an array of hash maps to find the longest arithmetic subsequence length for an input array of size n?

medium

A. O(n^3) due to triple nested loops checking all subsequences

B. O(n^2 * W) where W is the range of possible differences

C. O(n log n) by sorting and binary searching differences

D. O(n^2) because each pair (i, j) is processed once with constant-time hash map operations on average

Solution

1. Step 1: Identify loops and operations

   The code has two nested loops over n, and inside uses hash map get/set which is average O(1).

2. Step 2: Confirm no hidden factors

   Difference range W does not affect complexity since hash maps handle keys efficiently; no sorting or extra loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two nested loops with O(1) hash ops -> O(n^2) time [OK]

Hint: Two nested loops with hash map ops yield O(n^2) time [OK]

Common Mistakes:

• Confusing difference range W as multiplicative factor
• Assuming triple nested loops from brute force
• Thinking sorting is involved

5. What is the time complexity of the optimal sliding window solution for finding the longest substring with at most two distinct characters, assuming the input string length is n?

medium

A. O(n²), because the inner while loop can run up to n times for each character.

B. O(n * k), where k is the number of distinct characters allowed (here k=2).

C. O(n log n), due to maintaining a balanced data structure for frequencies.

D. O(n), because each character is visited at most twice by the left and right pointers.

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 distinct_count > 2, also at most n times.

2. Step 2: Confirm total operations

   Each character is processed at most twice (once when right pointer visits, once when left pointer moves), so total operations are O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window with two pointers is classic O(n) approach [OK]

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

Common Mistakes:

• Assuming nested loops multiply to O(n²)
• Confusing frequency map maintenance cost
• Thinking k affects complexity linearly