2Brute2Best
🔥0

Count Number of Nice Subarrays

Medium·LeetCode #1248 Pro OnlyBasic Reinforcement
LeetCode
01

Problem Statement

You are given an array of positive integers nums and a number k.

A contiguous subarray is called nice if it contains exactly k odd numbers. Count the nice subarrays.

Input

An integer array nums and an integer k.

Output

The number of contiguous subarrays that contain exactly k odd numbers.

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

Only [1,1,2,1] (indices 0..3) and [1,2,1,1] (indices 1..4) contain exactly 3 odd numbers.

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

There are no odd numbers at all, so no subarray has exactly 1.

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

A nice subarray must contain both 1s. It can start at any of the 4 positions up to the first 1, and end at any of the 4 positions from the second 1 onward: 4 × 4 = 16.

Constraints
  • • 1 ≤ nums.length ≤ 5 · 10^4
  • • 1 ≤ nums[i] ≤ 10^5
  • • 1 ≤ k ≤ nums.length
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“contiguous subarray”
→ We are counting ranges → window or prefix sum.
“exactly k odd numbers”
→ Only a yes/no property of each element matters → map it to 0/1, then it is a sum. "Exactly" → two at-most counts.
“count the subarrays”
→ Each right end adds a number of starts, `right − left + 1`.
03

Approach Complexity Ladder

Brute Force — try every startO(N²)O(1)

Fix each start, grow the end, count when the odd count hits k

Better — prefix odd count + mapO(N)O(N)

Count earlier prefixes with (odds so far − k) odd numbers

Optimal — atMost(k) − atMost(k − 1)O(N)O(1)

Treat odd as 1 and even as 0, then use two at-most windows

Brute Force Intuition

For every start, move the end to the right and keep a running count of odd numbers. Count one each time it equals k. The odd count only goes up, so stop once it passes k.

Recognition rule for this sub-pattern:

"Exactly K" is not monotonic, so a window can't count it directly. Use exactly(K) = atMost(K) − atMost(K − 1).
Remember this · Sliding Window
Trigger
Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".
Think
Can I keep a valid range and move it, instead of checking every subarray from scratch?
Key question
When is my current window valid?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track
C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track
Binary Subarrays With SumSubarrays with K Different Integers