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 — Hash Maps

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

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

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

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

3

Return the Total Count of Nice Subarrays

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

2 more steps with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

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

See the answer with Pro.

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`