Count Number of Nice Subarrays

LeetCode 1370 | Difficulty: Medium

Medium

Problem Description

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

Example 1:

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: 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
Explanation: 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

Constraints:

- `1 <= nums.length <= 50000`

- `1 <= nums[i] <= 10^5`

- `1 <= k <= nums.length`

Topics: Array, Hash Table, Math, Sliding Window, Prefix Sum

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 366 ms)

Metric	Value
Runtime	366 ms
Memory	46.7 MB
Date	2022-02-08

Solution

public class Solution {
    public int NumberOfSubarrays(int[] nums, int k) {
        return NiceAtMostK(nums,k) - NiceAtMostK(nums, k-1);
}

private int NiceAtMostK(int[] nums, int k)
{
    Dictionary<int, int> d = new Dictionary<int, int>();
    int result = 0;
    int i = 0;
    for (int j = 0; j < nums.Length; j++)
    {
        if(nums[j]%2==1) k--;
        while (k < 0)
        {
            if(nums[i]%2==1) k++;
            i++;
        }
        result += j - i + 1;
    }
    return result;
}
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Hash Map	$O(n)$	$O(n)$
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: After replacing each even by zero and every odd by one can we use prefix sum to find answer ?

Hint 2: Can we use two pointers to count number of sub-arrays ?

Hint 3: Can we store the indices of odd numbers and for each k indices count the number of sub-arrays that contains them ?