#1248

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Number of Nice Subarrays

The problem requires counting subarrays with exactly k odd numbers using an efficient array scanning approach.

array hash table math sliding window prefix sum

Problem Statement

You are given an array of integers nums and an integer k. A continuous subarray is considered nice if it contains exactly k odd numbers. Your task is to return the total number of nice subarrays in the given array.

For example, if nums = [1,1,2,1,1] and k = 3, the nice subarrays are [1,1,2,1] and [1,2,1,1]. Efficiently calculating the number of such subarrays is critical, as the array size can be large (up to 50,000).

Examples

Example 1

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

Output: 2

The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

Example 2

Input: nums = [2,4,6], k = 1

Output: 0

There are no odd numbers in the array.

Example 3

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

Output: 16

Example details omitted.

Constraints

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

Solution Approach

Transform the Problem

Transform each number in the array to 1 if it's odd and 0 if it's even. This reduces the problem to finding subarrays that sum to exactly k.

Use a Prefix Sum with Hash Lookup

As you scan through the array, maintain a prefix sum of the odd numbers seen so far. Use a hash table to store the frequency of each prefix sum. For each prefix sum, check how many times prefix_sum - k has been encountered. This gives the number of subarrays ending at the current index that contain exactly k odd numbers.

Efficient Calculation

By leveraging the prefix sum and hash map, you can calculate the number of nice subarrays in linear time, avoiding the need for a nested loop, which would be inefficient for large arrays.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity of the solution is O(n) because we only traverse the array once and perform constant-time operations (hash table lookups) for each element. The space complexity is O(1) because we only need a fixed amount of extra space for the prefix sum and hash table, regardless of the input size.

What Interviewers Usually Probe

Look for an understanding of prefix sums and hash map usage to solve the problem efficiently.
Candidates should be able to explain how transforming the problem with binary values simplifies finding subarrays with k odd numbers.
The candidate may struggle if they attempt brute force solutions without recognizing the need for optimization.

Common Pitfalls or Variants

Common pitfalls

Not transforming even numbers to zero and odd numbers to one, which can lead to an incorrect approach.
Attempting a brute-force solution that checks every subarray, which would be too slow for large inputs.
Not updating the hash map properly, which can lead to missing some valid subarrays or counting duplicates.

Follow-up variants

Count subarrays with at most k odd numbers, which can be achieved by a similar approach with a slight modification.
Count subarrays with exactly k even numbers by transforming the problem to focus on even numbers instead of odd ones.
Find the longest subarray with exactly k odd numbers by adjusting the approach to track the maximum length instead of counting subarrays.

FAQ

How do I approach solving the 'Count Number of Nice Subarrays' problem?

Start by transforming the odd numbers to 1 and the even numbers to 0, then use prefix sums and a hash map to efficiently count subarrays with exactly k odd numbers.

Can I solve this problem using brute force?

Brute force solutions are too slow for large inputs, so it's crucial to use a more efficient approach like prefix sums and hash map lookups to get an O(n) solution.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the input array, because we only traverse the array once and perform constant-time operations for each element.

What other variations of this problem should I practice?

You should practice problems that involve counting subarrays with certain properties, such as subarrays with at most k odd numbers or subarrays with k even numbers.

Why does using a hash map make the solution efficient?

The hash map allows you to store and quickly look up prefix sums, enabling you to count subarrays that sum to exactly k in constant time for each element in the array.

terminal

Solution

Solution 1: Prefix Sum + Array or Hash Table

The problem asks for the number of subarrays that contain exactly $k$ odd numbers. We can calculate the number of odd numbers $t$ in each prefix array and record it in an array or hash table $cnt$. For each prefix array, we only need to find the number of prefix arrays with $t-k$ odd numbers, which is the number of subarrays ending with the current prefix array.

1

2

3

4

5

6

7

8

9

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        cnt = Counter({0: 1})
        ans = t = 0
        for v in nums:
            t += v & 1
            ans += cnt[t - k]
            cnt[t] += 1
        return ans

Continue Practicing

#1442 count triplets that can form two arrays of equal xor #930 binary subarrays with sum #1658 minimum operations to reduce x to zero