What pattern does Count Number of Nice Subarrays use?

The Pattern: Hash Maps (Prefix Sum Frequency Counting) The Heuristic: When counting subarrays with a fixed sum or count, transform the problem into prefix sums and use a hash map to track frequencies of prefix sums, enabling O(1) lookups of complementary sums that form valid subarrays.

Count Number of Nice Subarrays - LeetCode Solution

Q: What is the time complexity of Count Number of Nice Subarrays?

O(n). The algorithm iterates through the array once, performing constant-time hash map operations for each element.

Problem

Given an integer array nums and an integer k, return the number of contiguous subarrays that have exactly k odd numbers.

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length

Example

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

Output: 2

The contiguous subarrays with exactly 3 odd numbers are [1,1,2,1] (indices 0–3) and [1,2,1,1] (indices 1–4). We keep a running count curr of how many odd numbers we have seen so far and a map counts that stores how many times each curr value has appeared. counts[0] = 1 at the start represents the empty prefix before the array, so subarrays that start at index 0 can be counted. Start with curr = 0, ans = 0, counts = {0: 1}. Index 0: num = 1 (odd), so curr becomes 1. curr - k = 1 - 3 = -2, which is not in counts, so ans stays 0. We record this prefix by setting counts[1] = 1. Index 1: num = 1 (odd), so curr becomes 2. curr - k = 2 - 3 = -1, which is still not in counts, so there is no subarray with 3 odds ending here. We update counts[2] = 1. Index 2: num = 2 (even), so curr stays 2. curr - k is still -1, so ans remains 0. We have now seen prefix sum 2 twice, so counts[2] = 2. Index 3: num = 1 (odd), so curr becomes 3. Now the key step happens: curr - k = 3 - 3 = 0, and counts[0] = 1. That means there is 1 previous prefix where the odd count was 0, so the subarray from index 0 to 3 ([1,1,2,1]) has exactly 3 odd numbers. We add counts[0] to ans, so ans becomes 1, and set counts[3] = 1. Index 4: num = 1 (odd), so curr becomes 4. Now curr - k = 4 - 3 = 1, and counts[1] = 1, so there is 1 previous prefix where the odd count was 1. That gives the subarray from index 1 to 4 ([1,2,1,1]) with exactly 3 odd numbers. We add counts[1] to ans, so ans becomes 2, and set counts[4] = 1. At the end, ans = 2, which is the number of subarrays that contain exactly 3 odd numbers.

Approach

Straightforward Solution

A brute-force approach would check every subarray and count odd numbers, resulting in O(n^2) time complexity, which is too slow for large inputs.

Core Observation

The problem reduces to counting subarrays where the difference between prefix sums of odd counts equals k. Each prefix sum represents how many odd numbers have been encountered up to the current index.

Path to Optimal

Recognizing that the count of odd numbers up to each index forms a prefix sum array, the problem becomes finding pairs of prefix sums where their difference is k. Using a hash map to store frequencies of prefix sums allows constant-time lookups, enabling a single pass solution.

Optimal Approach

Iterate through nums, updating the current prefix sum of odd counts. For each prefix sum curr, add counts[curr - k] to the answer, since each occurrence of curr - k represents a subarray ending at the current index with exactly k odd numbers. Update counts[curr] accordingly. This yields an O(n) time and O(n) space solution.

Time

O(n)

The algorithm iterates through the array once, performing constant-time hash map operations for each element.

Space

O(n)

The hash map stores frequencies of prefix sums, which in the worst case can be up to n distinct values.

Solution

1from collections import defaultdict
2
3class Solution:
  def numberOfSubarrays(self, nums: List[int], k: int) -> int:
      counts = defaultdict(int)
      counts[0] = 1
      ans = curr = 0
      
      for num in nums:
          curr += num % 2
          ans += counts[curr - k]
          counts[curr] += 1
13
      return ans

Step-by-Step Solution

1

Initialize Prefix Sum Frequency Map and Counters

5counts = defaultdict(int)
6counts[0] = 1
7ans = curr = 0

Objective

To set up a hash map to count frequencies of prefix sums and initialize counters for the answer and current prefix sum.

Key Insight

Starting counts[0] = 1 accounts for the empty prefix before processing any elements, enabling detection of subarrays starting at index 0. Initializing ans and curr to zero prepares for accumulation of results and tracking the running count of odd numbers.

Interview Quick-Check

Core Logic

counts[0] = 1 is critical to count subarrays that start from the beginning of the array.

State & Boundaries

Initialize ans and curr to zero to represent no subarrays counted and zero odd numbers seen initially.

2

Iterate Through nums to Count Valid Subarrays Using Prefix Sums

9for num in nums:
  curr += num % 2
  ans += counts[curr - k]
  counts[curr] += 1

Objective

To traverse the array, update the prefix sum of odd numbers, and accumulate the count of valid subarrays ending at each position.

Key Insight

For each number, increment curr by 1 if it is odd. The number of subarrays ending at the current index with exactly k odd numbers equals the frequency of prefix sums equal to curr - k. Updating counts[curr] after counting ensures future subarrays can be detected. This approach leverages the prefix sum difference property to count subarrays in O(n) time.

Interview Quick-Check

Core Logic

The key step is adding counts[curr - k] to ans, which counts all subarrays ending here with exactly k odd numbers.

State & Boundaries

Update counts[curr] after adding to ans to ensure the current prefix sum is available for future subarray counts.

Common Pitfalls & Bugs

Forgetting to initialize counts[0] = 1 or updating counts[curr] in the correct order can cause incorrect counts or missed subarrays.

3

Return the Total Count of Nice Subarrays

14	`return ans`

Objective

To return the accumulated count of subarrays with exactly k odd numbers after processing the entire array.

Key Insight

Returning ans completes the algorithm by providing the total number of valid subarrays found during the single pass.

Interview Quick-Check

Core Logic

Returning ans gives the final count of all subarrays with exactly k odd numbers.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 6 Critical

counts[0] = 1

Set the frequency of prefix sum zero to one.

This initialization accounts for the empty prefix before processing any elements, allowing subarrays starting at index 0 to be counted correctly.

Line 11 Critical

ans += counts[curr - k]

Add the count of prefix sums equal to curr - k to the answer.

This line is the core of the algorithm: it counts all subarrays ending at the current index that have exactly k odd numbers by leveraging the prefix sum difference property.

Line 10 Critical

curr += num % 2

Increment curr by 1 if the current number is odd, else by 0.

This line updates the prefix sum of odd numbers, which is the fundamental state used to identify subarrays with exactly k odd numbers.

Line 12 Core

counts[curr] += 1

Increment the frequency count of the current prefix sum.

Updating counts[curr] after counting ensures that future subarrays can be detected correctly, maintaining accurate frequency tracking.

Line 5 Core

counts = defaultdict(int)

Initialize a default dictionary to count frequencies of prefix sums.

Using a defaultdict(int) simplifies frequency counting by automatically initializing missing keys to zero, enabling clean and efficient updates.

Line 14 Core

return ans

Return the total count of subarrays with exactly k odd numbers.

Returning ans provides the final result after processing the entire array, completing the algorithm.

Line 7 Standard

ans = curr = 0

Initialize answer and current prefix sum counters to zero.

Starting ans and curr at zero sets the baseline for counting valid subarrays and tracking the number of odd numbers encountered so far.

Line 9 Standard

for num in nums:

Iterate over each number in the input array.

Processing each element sequentially is necessary to build prefix sums and count valid subarrays in a single pass.

Test Your Understanding

Why does checking counts[curr - k] give the number of subarrays ending at the current index with exactly k odd numbers?

Because curr represents the total number of odd numbers up to the current index, and curr - k represents the prefix sums where the count of odd numbers was exactly k less. The difference corresponds to subarrays with exactly k odd numbers.

Don't just read it. Drill it.

Reconstruct Count Number of Nice Subarrays from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Count Number of Nice Subarrays drill

or drill a free problem

1	`from collections import defaultdict`
2
3	`class Solution:`
4	`def numberOfSubarrays(self, nums: List[int], k: int) -> int:`
5	`counts = defaultdict(int)`
6	`counts[0] = 1`
7	`ans = curr = 0`
8
9	`for num in nums:`
10	`curr += num % 2`
11	`ans += counts[curr - k]`
12	`counts[curr] += 1`
13
14	`return ans`

9	`for num in nums:`
10	`curr += num % 2`
11	`ans += counts[curr - k]`
12	`counts[curr] += 1`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Prefix Sum Frequency Map and Counters

Iterate Through nums to Count Valid Subarrays Using Prefix Sums

Return the Total Count of Nice Subarrays

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.