Count Number of Nice Subarrays

Medium
251.

Count Number of Nice Subarrays

Count Number of Nice Subarrays is a medium coding problem on arrays, hash table and math, asked in Amazon and Google interviews.

Given an array of integers nums and an integer k, a subarray is nice if it contains exactly k odd numbers.

Return the number of nice subarrays.

Example 1

Input
nums = [1,1,2,1,1], k = 3
Output
2
Explanation
The nice subarrays are [1,1,2,1] and [1,2,1,1].

Example 2

Input
nums = [2,4,6], k = 1
Output
0
Explanation
There are no odd numbers at all.

Example 3

Input
nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output
16

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 1000
  • 1 <= k <= nums.length

Follow-up: Replace every number by its parity and this becomes 'count subarrays with sum k'.

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numberOfSubarrays = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Number of Nice Subarrays — Problem & Solution

Count Number of Nice Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Number of Nice Subarrays is a medium coding problem on arrays, hash table and math, asked in Amazon and Google interviews.

Problem statement

Given an array of integers nums and an integer k, a subarray is nice if it contains exactly k odd numbers.

Return the number of nice subarrays.

Example 1

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The nice subarrays are [1,1,2,1] and [1,2,1,1].

Example 2

Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There are no odd numbers at all.

Example 3

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

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 1000
  • 1 <= k <= nums.length

Follow-up: Replace every number by its parity and this becomes 'count subarrays with sum k'.

Hints for Count Number of Nice Subarrays

  1. Hint 1

    The actual values do not matter — only whether each element is odd.

  2. Hint 2

    Map odd to 1 and even to 0; a nice subarray is one summing to k.

  3. Hint 3

    Then it is the standard prefix-count trick, seeded with {0: 1}.

How to solve Count Number of Nice Subarrays

Only parity matters: map odd to 1 and even to 0, then count subarrays summing to k with the prefix-count trick.

Approach

  1. Maintain count[oddPrefix] seeded with {0: 1}.
  2. For each element, add x % 2 to the running odd count and add count[odds - k] to the answer.
  3. Increment count[odds].

Why it works

A subarray has exactly k odds iff its two bounding prefixes differ by k in odd count, so the map lookup counts each nice subarray ending at the current index.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Use x % 2, not x & 1, in languages where negative odd numbers produce -1 under % — or take abs first.

Reference solution

Python

def numberOfSubarrays(nums, k: int) -> int:
    count = {0: 1}
    odds = answer = 0
    for x in nums:
        odds += x % 2
        answer += count.get(odds - k, 0)
        count[odds] = count.get(odds, 0) + 1
    return answer

Java

public static int numberOfSubarrays(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);
    int odds = 0, total = 0;
    for (int v : nums) {
        odds += v % 2;
        total += count.getOrDefault(odds - k, 0);
        count.put(odds, count.getOrDefault(odds, 0) + 1);
    }
    return total;
}

C++

int numberOfSubarrays(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    count[0] = 1;
    int odds = 0, total = 0;
    for (int v : nums) {
        odds += v % 2;
        auto it = count.find(odds - k);
        if (it != count.end()) total += it->second;
        count[odds]++;
    }
    return total;
}

JavaScript

var numberOfSubarrays = function(nums, k) {
    const count = new Map();
    count.set(0, 1);
    let odds = 0, total = 0;
    for (let i = 0; i < nums.length; i++) {
        odds += nums[i] % 2;
        total += count.get(odds - k) || 0;
        count.set(odds, (count.get(odds) || 0) + 1);
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets