Count Number of Nice Subarrays — LC 1248 Exactly K Sliding Window

Problem Statement#

Given an integer array nums and integer k, count the contiguous subarrays containing exactly k odd numbers.

Constraints:

• 1 less than or equal to nums.length less than or equal to 50000
• 1 less than or equal to nums[i] less than or equal to 10 to the 5
• 1 less than or equal to k less than or equal to nums.length

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

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

Why This Problem Matters#

LeetCode 1248 — Count Number of Nice Subarrays is asked at Google, Amazon, and TikTok because it teaches the universal "exactly k" sliding window trick. Once you internalize that exactly k equals atMost(k) minus atMost(k - 1), you can solve a dozen variants on autopilot: LC 992 (Subarrays with K Different Integers), LC 930 (Binary Subarrays with Sum), and LC 1358 (Number of Substrings Containing All Three Characters) all bow to the same pattern.

The problem also doubles as a parity exercise. Recognizing that odd or even is a 0/1 indicator lets you reframe the problem as "count subarrays whose indicator sum equals k", which is identical to LC 930.

In real systems, this maps to log analysis where you count windows containing exactly k error events, or to A/B test cohorts where you need exactly k qualifying actions in a rolling window.

The Core Insight#

Direct counting of subarrays with exactly k odd numbers is hard because the boundaries are not monotonic. But "at most k odd numbers" is monotonic: as right advances, you can shrink left until the count drops to k or below, and every subarray inside that window has at most k odds.

Define atMost(k) as the number of subarrays with at most k odd numbers. Then:

exactly(k) equals atMost(k) minus atMost(k minus 1).

Each atMost call is a clean O(n) sliding window. Two calls give a total O(n) solution with O(1) extra space.

The counting trick inside atMost: when the window [left, right] is valid, every subarray ending at right and starting in [left, right] is valid, so add right - left + 1.

Visual Dry Run#

Input: nums = [1, 1, 2, 1, 1], k = 3. Compute atMost(3) and atMost(2).

atMost(3) is 14, atMost(2) is 12, answer 14 minus 12 equals 2.

Solution (Optimal)#

class Solution:
    def numberOfSubarrays(self, nums, k):
        def at_most(limit):
            if limit < 0:
                return 0
            left, count, total = 0, 0, 0
            for right, value in enumerate(nums):
                if value % 2 == 1:
                    count += 1
                while count > limit:
                    if nums[left] % 2 == 1:
                        count -= 1
                    left += 1
                total += right - left + 1
            return total
        return at_most(k) - at_most(k - 1)

var numberOfSubarrays = function(nums, k) {
    const atMost = (limit) => {
        if (limit < 0) return 0;
        let left = 0, count = 0, total = 0;
        for (let right = 0; right < nums.length; right++) {
            if (nums[right] % 2 === 1) count++;
            while (count > limit) {
                if (nums[left] % 2 === 1) count--;
                left++;
            }
            total += right - left + 1;
        }
        return total;
    };
    return atMost(k) - atMost(k - 1);
};

Time: O(n) — two linear sliding windows. Space: O(1) — counters and indices only.

Common Mistakes#

• Trying to maintain an exact-k window directly. The window is not monotonic, so two-pointer collapses.
• Forgetting the limit less than 0 guard. atMost(-1) should return 0, not iterate.
• Miscounting with right - left instead of right - left + 1.
• Treating odd-detection as value & 1 without parentheses, causing precedence bugs in some languages.
• Re-running atMost with a side effect that mutates global state.

Interview Tips#

• Lead with the trick: "Exactly k equals atMost(k) minus atMost(k - 1)."
• Note that you reuse the same helper twice — emphasizes code reuse.
• Walk through atMost on a small array before coding.
• Mention the alternative prefix-sum approach for breadth.
• Ask if the array can contain only even numbers; if so, atMost(k) is n times (n + 1) / 2 for k greater than 0 and the answer is 0.

Follow-up Questions#

• Solve with prefix sums and a hashmap instead. Treat odd as 1, count (prefix[i] - k) matches.
• What if elements are floating point? Replace parity with a custom predicate.
• What if you must return the actual subarrays? Track windows during atMost(k) and exclude those captured in atMost(k - 1).
• How would you parallelize this on a huge stream? Run atMost as a state machine and merge counts on chunk boundaries.
• Variant: count subarrays with exactly k zeros — same template, different predicate.

Key Takeaways#

• LeetCode 1248 — Count Number of Nice Subarrays is solved in O(n) using two sliding windows.
• exactly(k) equals atMost(k) minus atMost(k minus 1) is the universal "exact count" trick.
• Counting trick right - left + 1 adds all valid subarrays ending at right.
• The same template solves LC 992, LC 930, and LC 1358.
• Parity check value mod 2 equals 1 makes the problem identical to LC 930.
• Asked at Google, Amazon, and TikTok in array and sliding window rounds.
• Always guard atMost(-1) to avoid invalid loops.