Count Number of Nice Subarrays

🎯

Count Number of Nice Subarrays

mediumHASH_MAPAmazonGoogle

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.

💡 This problem is about counting subarrays with a specific property (exactly k odd numbers). Beginners often struggle because they try to check every subarray explicitly, which is inefficient. The key insight is to track counts of prefix sums and use a hashmap to count valid subarrays efficiently.

📋

Problem Statement

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

💡

Example

Input"nums = [1,1,2,1,1], k = 3"

Output2

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

• All elements are even → output 0
• All elements are odd and k equals array length → output 1
• k = 1 and array has multiple odd numbers separated by evens → count each single odd subarray
• Array length = 1 and k = 1 → output 1 if element is odd, else 0

⚠️

Common Mistakes

Counting subarrays with exactly k odd numbers by checking all subarrays without pruning

Code runs too slowly and times out on large inputs

✅ Use prefix sums and hashmap or sliding window to optimize counting

Forgetting to initialize hashmap with count[0] = 1

Misses counting subarrays starting at index 0, leading to incorrect results

✅ Always initialize count[0] = 1 before iteration

Using '>' instead of '>=' when shrinking window in sliding window approach

Window shrinks incorrectly, causing wrong counts

✅ Use 'while odd_count > k' condition to shrink window properly

Not handling k=0 or k=1 edge cases separately

Code may produce wrong results or errors when k=0 or k=1

✅ Ensure code handles k=1 and k=0 correctly, especially in sliding window difference calculation

Using modulo operator incorrectly or forgetting to check oddness

Incorrect odd count leading to wrong results

✅ Always check 'num % 2 == 1' to identify odd numbers

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by explicitly checking every subarray. Though inefficient, it clarifies what exactly we are counting and why optimization is needed.

Intuition

Check every possible subarray and count how many odd numbers it contains. If the count equals k, increment the result.

Algorithm

1. Initialize a result counter to 0.
2. Use two nested loops to consider every subarray: outer loop for start index, inner loop for end index.
3. For each subarray, count the number of odd numbers.
4. If the count equals k, increment the result.

💡 The nested loops and counting inside the inner loop make it clear what we are looking for, but also show why this approach is slow for large inputs.

</>

Code

def count_nice_subarrays(nums, k):
    n = len(nums)
    result = 0
    for start in range(n):
        odd_count = 0
        for end in range(start, n):
            if nums[end] % 2 == 1:
                odd_count += 1
            if odd_count == k:
                result += 1
            elif odd_count > k:
                break
    return result

# Driver code
if __name__ == '__main__':
    print(count_nice_subarrays([1,1,2,1,1], 3))  # Output: 2

Line Notes

for start in range(n):Outer loop picks the start index of subarray

odd_count = 0Reset odd count for each new start index

for end in range(start, n):Inner loop extends subarray to the right

if nums[end] % 2 == 1:Check if current element is odd to update count

if odd_count == k:If exactly k odds, increment result

elif odd_count > k:No need to continue if odd count exceeded k

public class Solution {
    public int countNiceSubarrays(int[] nums, int k) {
        int n = nums.length;
        int result = 0;
        for (int start = 0; start < n; start++) {
            int oddCount = 0;
            for (int end = start; end < n; end++) {
                if (nums[end] % 2 == 1) {
                    oddCount++;
                }
                if (oddCount == k) {
                    result++;
                } else if (oddCount > k) {
                    break;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countNiceSubarrays(new int[]{1,1,2,1,1}, 3)); // Output: 2
    }
}

Line Notes

for (int start = 0; start < n; start++) {Outer loop selects subarray start

int oddCount = 0;Reset odd count for each start

for (int end = start; end < n; end++) {Inner loop extends subarray

if (nums[end] % 2 == 1) {Check if element is odd

if (oddCount == k) {Increment result if exactly k odds

else if (oddCount > k) {Stop early if odd count exceeded

#include <iostream>
#include <vector>
using namespace std;

int countNiceSubarrays(vector<int>& nums, int k) {
    int n = nums.size();
    int result = 0;
    for (int start = 0; start < n; start++) {
        int oddCount = 0;
        for (int end = start; end < n; end++) {
            if (nums[end] % 2 == 1) {
                oddCount++;
            }
            if (oddCount == k) {
                result++;
            } else if (oddCount > k) {
                break;
            }
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1,1,2,1,1};
    cout << countNiceSubarrays(nums, 3) << endl; // Output: 2
    return 0;
}

Line Notes

for (int start = 0; start < n; start++) {Outer loop picks subarray start index

int oddCount = 0;Reset odd count for each new start

for (int end = start; end < n; end++) {Inner loop extends subarray to the right

if (nums[end] % 2 == 1) {Check if current element is odd

if (oddCount == k) {Increment result when exactly k odds found

else if (oddCount > k) {Break early to avoid unnecessary checks

function countNiceSubarrays(nums, k) {
    const n = nums.length;
    let result = 0;
    for (let start = 0; start < n; start++) {
        let oddCount = 0;
        for (let end = start; end < n; end++) {
            if (nums[end] % 2 === 1) {
                oddCount++;
            }
            if (oddCount === k) {
                result++;
            } else if (oddCount > k) {
                break;
            }
        }
    }
    return result;
}

// Test
console.log(countNiceSubarrays([1,1,2,1,1], 3)); // Output: 2

Line Notes

for (let start = 0; start < n; start++) {Outer loop selects subarray start

let oddCount = 0;Reset odd count for each start index

for (let end = start; end < n; end++) {Inner loop extends subarray

if (nums[end] % 2 === 1) {Check if element is odd

if (oddCount === k) {Increment result if exactly k odds

else if (oddCount > k) {Stop inner loop early if odd count exceeded

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, so O(n^2). No extra space except counters.

💡 For n=20, this means up to 400 operations, which is okay, but for n=100000 it becomes 10 billion operations, which is too slow.

Interview Verdict: TLE

This approach times out on large inputs, showing the need for a more efficient method.

🧠

Prefix Sum + HashMap Counting

💡 This approach introduces prefix sums to track the count of odd numbers up to each index, and uses a hashmap to count how many prefix sums differ by k, enabling efficient counting of valid subarrays.

Intuition

Transform the problem into counting how many prefix sums differ by k. Use a hashmap to store frequencies of prefix sums and count valid subarrays in O(n) time.

Algorithm

1. Initialize a hashmap with {0:1} to count prefix sums frequencies.
2. Initialize odd_count and result to 0.
3. Iterate through nums, increment odd_count if current number is odd.
4. Check if (odd_count - k) exists in hashmap; if yes, add its frequency to result.
5. Increment frequency of odd_count in hashmap.
6. Return result.

💡 The hashmap stores how many times each prefix sum has appeared, allowing quick lookup of how many subarrays end at current index with exactly k odds.

</>

Code

from collections import defaultdict

def count_nice_subarrays(nums, k):
    count = defaultdict(int)
    count[0] = 1
    odd_count = 0
    result = 0
    for num in nums:
        if num % 2 == 1:
            odd_count += 1
        if odd_count - k in count:
            result += count[odd_count - k]
        count[odd_count] += 1
    return result

# Driver code
if __name__ == '__main__':
    print(count_nice_subarrays([1,1,2,1,1], 3))  # Output: 2

Line Notes

count = defaultdict(int)Initialize hashmap to store prefix sums frequencies

count[0] = 1Base case: zero odd numbers seen once before starting

for num in nums:Iterate over each number in array

if num % 2 == 1:Increment odd count if current number is odd

if odd_count - k in count:Check if a prefix sum k less than current exists

result += count[odd_count - k]Add number of valid subarrays ending here

count[odd_count] += 1Update frequency of current prefix sum

import java.util.HashMap;

public class Solution {
    public int countNiceSubarrays(int[] nums, int k) {
        HashMap<Integer, Integer> count = new HashMap<>();
        count.put(0, 1);
        int oddCount = 0, result = 0;
        for (int num : nums) {
            if (num % 2 == 1) {
                oddCount++;
            }
            result += count.getOrDefault(oddCount - k, 0);
            count.put(oddCount, count.getOrDefault(oddCount, 0) + 1);
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countNiceSubarrays(new int[]{1,1,2,1,1}, 3)); // Output: 2
    }
}

Line Notes

HashMap<Integer, Integer> count = new HashMap<>();HashMap to store prefix sums frequencies

count.put(0, 1);Initialize base case for zero odd count

for (int num : nums) {Iterate over array elements

if (num % 2 == 1) {Increment odd count if odd number found

result += count.getOrDefault(oddCount - k, 0);Add count of prefix sums that differ by k

count.put(oddCount, count.getOrDefault(oddCount, 0) + 1);Update frequency of current odd count

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int countNiceSubarrays(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    count[0] = 1;
    int oddCount = 0, result = 0;
    for (int num : nums) {
        if (num % 2 == 1) {
            oddCount++;
        }
        if (count.find(oddCount - k) != count.end()) {
            result += count[oddCount - k];
        }
        count[oddCount]++;
    }
    return result;
}

int main() {
    vector<int> nums = {1,1,2,1,1};
    cout << countNiceSubarrays(nums, 3) << endl; // Output: 2
    return 0;
}

Line Notes

unordered_map<int, int> count;Hash map to store prefix sums frequencies

count[0] = 1;Base case: zero odd count seen once

for (int num : nums) {Iterate over each element

if (num % 2 == 1) {Increment odd count if odd

if (count.find(oddCount - k) != count.end()) {Check if prefix sum k less exists

result += count[oddCount - k];Add valid subarray counts

count[oddCount]++;Update frequency of current odd count

function countNiceSubarrays(nums, k) {
    const count = new Map();
    count.set(0, 1);
    let oddCount = 0, result = 0;
    for (const num of nums) {
        if (num % 2 === 1) {
            oddCount++;
        }
        result += count.get(oddCount - k) || 0;
        count.set(oddCount, (count.get(oddCount) || 0) + 1);
    }
    return result;
}

// Test
console.log(countNiceSubarrays([1,1,2,1,1], 3)); // Output: 2

Line Notes

const count = new Map();Map to store prefix sums frequencies

count.set(0, 1);Initialize base case for zero odd count

for (const num of nums) {Iterate over array elements

if (num % 2 === 1) {Increment odd count if odd number

result += count.get(oddCount - k) || 0;Add counts of prefix sums differing by k

count.set(oddCount, (count.get(oddCount) || 0) + 1);Update frequency of current odd count

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass through array with hashmap lookups and updates in O(1) average time. Hashmap size up to n.

💡 For n=100000, this means about 100000 operations, which is efficient and practical.

Interview Verdict: Accepted

This approach is efficient and passes all tests, making it the preferred solution in interviews.

🧠

Sliding Window with Two Pointers

💡 This approach uses two pointers to find the number of subarrays with exactly k odd numbers by counting subarrays with at most k and at most k-1 odd numbers and subtracting them.

Intuition

Number of subarrays with exactly k odd numbers = number with at most k odds - number with at most k-1 odds. Use sliding window to count at most k odd subarrays efficiently.

Algorithm

1. Define a helper function to count subarrays with at most k odd numbers using two pointers.
2. Initialize two pointers and a count of odd numbers in the window.
3. Expand right pointer, update odd count.
4. Shrink left pointer while odd count exceeds k.
5. Sum counts of valid subarrays ending at each right pointer.
6. Return count(at most k) - count(at most k-1) as final result.

💡 This approach cleverly uses the difference of two counts to find exact matches, avoiding explicit enumeration of all subarrays.

</>

Code

def at_most_k(nums, k):
    left = 0
    count = 0
    odd_count = 0
    for right in range(len(nums)):
        if nums[right] % 2 == 1:
            odd_count += 1
        while odd_count > k:
            if nums[left] % 2 == 1:
                odd_count -= 1
            left += 1
        count += right - left + 1
    return count

def count_nice_subarrays(nums, k):
    return at_most_k(nums, k) - at_most_k(nums, k - 1)

# Driver code
if __name__ == '__main__':
    print(count_nice_subarrays([1,1,2,1,1], 3))  # Output: 2

Line Notes

def at_most_k(nums, k):Helper counts subarrays with at most k odd numbers

left = 0Initialize left pointer of sliding window

if nums[right] % 2 == 1:Increment odd count when odd found

while odd_count > k:Shrink window from left if too many odds

count += right - left + 1Add number of valid subarrays ending at right

return at_most_k(nums, k) - at_most_k(nums, k - 1)Difference gives count of exactly k odd subarrays

public class Solution {
    private int atMostK(int[] nums, int k) {
        int left = 0, count = 0, oddCount = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] % 2 == 1) {
                oddCount++;
            }
            while (oddCount > k) {
                if (nums[left] % 2 == 1) {
                    oddCount--;
                }
                left++;
            }
            count += right - left + 1;
        }
        return count;
    }

    public int countNiceSubarrays(int[] nums, int k) {
        return atMostK(nums, k) - atMostK(nums, k - 1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countNiceSubarrays(new int[]{1,1,2,1,1}, 3)); // Output: 2
    }
}

Line Notes

private int atMostK(int[] nums, int k) {Helper counts subarrays with at most k odd numbers

int left = 0, count = 0, oddCount = 0;Initialize pointers and counters

if (nums[right] % 2 == 1) {Increment odd count if odd number found

while (oddCount > k) {Shrink window from left if too many odds

count += right - left + 1;Add valid subarrays ending at right

return atMostK(nums, k) - atMostK(nums, k - 1);Difference gives exact count

#include <iostream>
#include <vector>
using namespace std;

int atMostK(const vector<int>& nums, int k) {
    int left = 0, count = 0, oddCount = 0;
    for (int right = 0; right < (int)nums.size(); right++) {
        if (nums[right] % 2 == 1) {
            oddCount++;
        }
        while (oddCount > k) {
            if (nums[left] % 2 == 1) {
                oddCount--;
            }
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

int countNiceSubarrays(vector<int>& nums, int k) {
    return atMostK(nums, k) - atMostK(nums, k - 1);
}

int main() {
    vector<int> nums = {1,1,2,1,1};
    cout << countNiceSubarrays(nums, 3) << endl; // Output: 2
    return 0;
}

Line Notes

int atMostK(const vector<int>& nums, int k) {Helper counts subarrays with at most k odd numbers

int left = 0, count = 0, oddCount = 0;Initialize pointers and counters

if (nums[right] % 2 == 1) {Increment odd count if odd

while (oddCount > k) {Shrink window from left if too many odds

count += right - left + 1;Add valid subarrays ending at right

return atMostK(nums, k) - atMostK(nums, k - 1);Difference gives exact count

function atMostK(nums, k) {
    let left = 0, count = 0, oddCount = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] % 2 === 1) {
            oddCount++;
        }
        while (oddCount > k) {
            if (nums[left] % 2 === 1) {
                oddCount--;
            }
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

function countNiceSubarrays(nums, k) {
    return atMostK(nums, k) - atMostK(nums, k - 1);
}

// Test
console.log(countNiceSubarrays([1,1,2,1,1], 3)); // Output: 2

Line Notes

function atMostK(nums, k) {Helper counts subarrays with at most k odd numbers

let left = 0, count = 0, oddCount = 0;Initialize pointers and counters

if (nums[right] % 2 === 1) {Increment odd count if odd

while (oddCount > k) {Shrink window from left if too many odds

count += right - left + 1;Add valid subarrays ending at right

return atMostK(nums, k) - atMostK(nums, k - 1);Difference gives exact count

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most twice by left and right pointers, so O(n) time. Only constant extra space used.

💡 For n=100000, this means about 200000 operations, which is efficient and uses less memory than hashmap.

Interview Verdict: Accepted

This approach is efficient and uses constant space, making it a good alternative in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the prefix sum + hashmap approach (Approach 2) as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Prefix Sum + HashMap	O(n)	O(n)	No	N/A	Preferred solution to code in interviews
3. Sliding Window	O(n)	O(1)	No	N/A	Good alternative if asked for space optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force to show understanding, and finally present the optimal solution with prefix sums and hashmap or sliding window.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding of what is being counted.Step 3: Explain why brute force is inefficient and introduce prefix sums with hashmap.Step 4: Present the prefix sum + hashmap solution with code.Step 5: Optionally, discuss the sliding window approach as an alternative.Step 6: Test your code with sample and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to recognize prefix sums and hashmap usage, optimize nested loops, and handle edge cases correctly.

Common Follow-ups

• What if we want subarrays with at most k odd numbers? → Use the atMostK helper function directly.
• Can you solve this with O(1) space? → Sliding window approach achieves this.

💡 These follow-ups test your understanding of variations and space optimization.

🔍

Pattern Recognition

When to Use

Use this pattern when you need to count subarrays with exactly k occurrences of a certain property (like odd numbers), and prefix sums or counts can be tracked.

Signature Phrases

'exactly k odd numbers''count number of subarrays''prefix sums of odd counts'

NOT This Pattern When

Problems that require maximum/minimum subarray sums or longest subarray length without exact count constraints

Similar Problems

Subarray Sum Equals K - uses prefix sums and hashmap to count subarrays with sum kNumber of Subarrays with Bounded Maximum - counts subarrays with constraints using sliding windowCount Number of Subarrays with Exactly K Odd Numbers - variant of this problem

Practice

1. What is the time complexity of the optimal prefix sum with hash map solution for finding the longest contiguous subarray with equal number of 0s and 1s, given an input array of length n?

medium

A. O(n) because each element is processed once with constant-time hash map operations

B. O(n) but with O(n²) space for storing all prefix sums

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

D. O(n²) due to nested loops scanning subarrays

Solution

1. Step 1: Identify the single loop over the array

   The algorithm iterates once over n elements, updating prefix_sum and hash map.

2. Step 2: Confirm hash map operations are O(1) average

   Insertion and lookup in hash map are average O(1), so total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is O(n²), no sorting involved, space is O(n) not O(n²) [OK]

Hint: Hash map lookups are average O(1), single pass over array [OK]

Common Mistakes:

• Confusing brute force O(n²) with optimal
• Assuming hash map is O(log n)
• Overestimating space complexity

2. What is the time complexity of the optimal sliding window solution for the Minimum Operations to Reduce X to Zero problem, assuming the input array length is n?

medium

A. O(n^2) due to nested loops for adjusting window boundaries.

B. O(n) for the main loop plus O(n) for sum computations inside the loop.

C. O(n) because each element is visited at most twice by left and right pointers.

D. O(n log n) due to sorting or binary search steps.

Solution

1. Step 1: Analyze the main loop and window adjustments

   The right pointer moves from 0 to n-1 once, and the left pointer only moves forward when shrinking the window, so each element is visited at most twice.

2. Step 2: Confirm no nested loops causing quadratic time

   While loop inside the for loop advances left pointer without resetting, so total moves of left pointer ≤ n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer sliding window runs in linear time [OK]

Hint: Sliding window moves pointers linearly [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Forgetting that left pointer only moves forward
• Confusing sum computations as extra loops

3. Identify the bug in the following code snippet for the Minimum Operations to Reduce X to Zero problem:

medium

A. Line with 'if target == 0: return -1' should return len(nums) instead.

B. The while loop condition should be 'current_sum >= target' instead of '>'.

C. The initialization of max_len should be 0 instead of -1.

D. The final return should be 'max_len' instead of 'len(nums) - max_len'.

Solution

1. Step 1: Understand the edge case when target == 0

   If target == 0, it means totalSum == x, so removing all elements is needed, so minimum operations = length of array.

2. Step 2: Identify incorrect return value

   The code returns -1 incorrectly, which signals no solution, but the correct answer is to remove all elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning -1 here causes wrong output on full removal case [OK]

Hint: Check edge cases where x equals total sum [OK]

Common Mistakes:

• Returning -1 instead of full length when target == 0
• Misinterpreting no solution vs full removal
• Ignoring edge cases in initial checks

4. What is the time complexity of the optimal prefix sum with array approach for finding the longest subarray with equal number of 0s and 1s, given an input array of length n?

medium

A. O(n) because each element is processed once with constant-time hash map lookups

B. O(n) with additional O(n) space for prefix sums and first occurrence array

C. O(n log n) due to sorting prefix sums

D. O(n^2) due to nested loops checking all subarrays

Solution

1. Step 1: Identify the main loop runs once over n elements.

   Each iteration does constant time work updating prefix sums and array lookups.

2. Step 2: Recognize space usage for prefix sums and first_occurrence array is O(n).

   Time is O(n), space is O(n), so total complexity includes both.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is O(n²), no sorting involved [OK]

Hint: Linear scan with O(n) space for prefix sums [OK]

Common Mistakes:

• Confusing brute force O(n²) with optimal
• Assuming sorting is needed
• Ignoring auxiliary space

5. Suppose the problem is modified so that the input array can contain duplicate numbers and you want to find the length of the longest consecutive sequence considering duplicates as separate elements (e.g., [1,2,2,3] counts as length 4). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Use a hash map to store counts of each number and sum counts for consecutive numbers to find the longest run.

B. Use the original hash set approach but multiply the length by the count of duplicates for each number.

C. Sort the array and count consecutive runs including duplicates by scanning linearly.

D. Ignore duplicates and apply the original hash set approach since duplicates don't affect sequence length.

Solution

1. Step 1: Understand the variant

   Duplicates count as separate elements, so sequences can include repeated numbers increasing length.

2. Step 2: Evaluate approaches

   Original hash set approach ignores duplicates; multiplying length by counts is incorrect because duplicates may be non-consecutive; sorting and scanning works but is O(n log n).

3. Step 3: Correct approach

   Using a hash map to store counts allows summing counts of consecutive numbers to find the longest run including duplicates efficiently.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map counting handles duplicates correctly and efficiently [OK]

Hint: Count duplicates explicitly using a hash map [OK]

Common Mistakes:

• Ignoring duplicates
• Multiplying length by counts incorrectly
• Assuming sorting is always best