Log inSign up
mediumLeetCodeNot Started

Count Number of Nice Subarrays

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 · Standard Array with 3 Odds:

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

Example 2 · No Subarray Has Enough Odds:

Input: nums = [2, 4, 6], k = 1
Output: 0
Explanation: There are no odd numbers in the array, so 0 nice subarrays.

Example 3 · Multiple Even Padding:

Input: nums = [2, 2, 2, 1, 2, 2, 1, 2, 2, 2], k = 2
Output: 16
Explanation: Any subarray containing both 1s and any combinations of surrounding 2s is valid (4 choices on left * 4 choices on right = 16).

Constraints:

  • 1 <= nums.length <= 50000
  • 1 <= nums[i] <= 105
  • 1 <= k <= nums.length

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Sliding Window fundamentals
  • Subarray Sum Equals K pattern
  • Prefix sum frequency counting

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the exact(k) = atMost(k) - atMost(k-1) sliding window paradigm.
  • Understand reduction of parity problems to binary 0/1 prefix sum queries.
  • Analyze space-optimal vs table-lookup trade-offs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Subarrays with K Different IntegersBinary Subarrays With SumSubarray Sum Equals K

1. Nested Loops Counting (Brute Force)

Intuition

Inspect every possible subarray (i, j) and count how many odd numbers it contains.

Algorithm

  1. 1. Initialize ans = 0.
  2. 2. Loop i from 0 to N-1: - oddCount = 0 - Loop j from i to N-1: - if nums[j] % 2 != 0: oddCount++ - if oddCount == k: ans++ - else if oddCount > k: break.
  3. 3. Return ans.

Brute Force All Subarrays Odd Tally Scan

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 1, 2, 1, 1]
Current operationSTEP 1 OF 6
Phase 1 — Not nice Advance j to 3: Step 1: Subarray [1, 1, 2] contains 2 odds
Visual state
Values and pointers at this exact step
array
S
1
1
2
1
1
0
↑ i=0
1
2
↑ j=2
3
4
Variables at this step
i
0
j
2
odds
2
k
3
niceCount
0
Check / comparison
Subarray [1, 1, 2]: odd elements are 1, 1 (count = 2). 2 != k (3).
Decision / next transition
Not nice. Advance j to 3.
Why this step matters

Phase 1 — Not nice Advance j to 3: Step 1: Subarray [1, 1, 2] contains 2 odds. Target is k = 3. Increment j.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Brute Force Approach: Nested Loops Counting
6int numberOfSubarrays(const vector<int>& nums, int k) {
7 int n = nums.size();
8 int ans = 0;
9 for (int i = 0; i < n; i++) {
10 int oddCount = 0;
11 for (int j = i; j < n; j++) {
12 if (nums[j] % 2 != 0) oddCount++;
13 if (oddCount == k) ans++;
14 else if (oddCount > k) break;
15 }
16 }
17 return ans;
18}
19
20int main() {
21 vector<int> nums = {1, 1, 2, 1, 1};
22 int k = 3;
23 int result = numberOfSubarrays(nums, k);
24 cout << "Output: " << result << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(N^2) — Nested loops test up to N*(N+1)/2 subarrays.
  • Space complexity: O(1) — Only scalar counters are used.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Prefix Odd-Count Frequency Array (Better)

Intuition

Transform into Prefix Sum problem and track prefix frequencies in an array.

Algorithm

  1. 1. Create prefixCount array of size N+1, initialize prefixCount[0] = 1.
  2. 2. Maintain curOdds = 0, ans = 0.
  3. 3. For each num in nums: - curOdds += num % 2 - if curOdds >= k: ans += prefixCount[curOdds - k] - prefixCount[curOdds]++.
  4. 4. Return ans.

Prefix Parity Count Hash Map

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [1, 1, 2, 1, 1]
Current operationSTEP 1 OF 7
Phase 1 — Step 1: Step 1: Convert each number to its parity (x % 2)
Visual state
Values and pointers at this exact step
array
S
1
1
2
1
1
0
↑ Init Map
1
2
3
4
Variables at this step
map
{ 0: 1 }
oddCount
0
total
0
Check / comparison
Treat array as binary: 1 for odd, 0 for even. Problem reduces to Subarray Sum Equals K!
Decision / next transition
Initialize map = { 0: 1 }, oddCount = 0, total = 0.
Why this step matters

Phase 1 — Step 1: Step 1: Convert each number to its parity (x % 2). The problem is now identically Subarray Sum Equals K! Initialize map = { 0: 1 }.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Better Approach: Prefix Odd-Count Frequency Array
6int numberOfSubarrays(const vector<int>& nums, int k) {
7 int n = nums.size();
8 vector<int> count(n + 1, 0);
9 count[0] = 1;
10 int curOdds = 0, ans = 0;
11
12 for (int x : nums) {
13 curOdds += (x % 2);
14 if (curOdds >= k) {
15 ans += count[curOdds - k];
16 }
17 count[curOdds]++;
18 }
19 return ans;
20}
21
22int main() {
23 vector<int> nums = {1, 1, 2, 1, 1};
24 int k = 3;
25 int result = numberOfSubarrays(nums, k);
26 cout << "Output: " << result << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass through nums with O(1) array index lookups.
  • Space complexity: O(N) — prefixCount array of size N+1 requires O(N) space.

3. Sliding Window AtMost(k) - AtMost(k-1) (Optimal)

Intuition

Compute exact count in O(N) time and O(1) space using the standard AtMost sliding window subtraction pattern.

Algorithm

  1. 1. Define helper function atMost(nums, goal): - If goal < 0, return 0 - Maintain l = 0, count = 0, ans = 0 - For r from 0 to N-1: - count += nums[r] % 2 - while count > goal: count -= nums[l++] % 2 - ans += (r - l + 1) - return ans.
  2. 2. Return atMost(nums, k) - atMost(nums, k - 1).

3-Pointer Sliding Window (Prefix Evens Accumulator)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 1, 2, 1, 1]
Current operationSTEP 1 OF 6
Phase 1 — Expand window to include 3rd odd: Step 1: Expand R until window contains k = 3 odd numbers
Visual state
Values and pointers at this exact step
array
S
1
1
2
1
1
0
↑ L=0
1
2
↑ R=2
3
4
Variables at this step
L
0
R
2
odds
2
count
0
total
0
Check / comparison
Initialize L=0, count=0, total=0. Expand R through indices 0..2. Odd count = 2 < 3.
Decision / next transition
Expand window to include 3rd odd.
Why this step matters

Phase 1 — Expand window to include 3rd odd: Step 1: Expand R until window contains k = 3 odd numbers. Indices 0..2 have 2 odds.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Optimal Approach: Sliding Window AtMost(k) - AtMost(k-1)
6int atMost(const vector<int>& nums, int goal) {
7 if (goal < 0) return 0;
8 int l = 0, count = 0, ans = 0;
9 for (int r = 0; r < nums.size(); r++) {
10 count += (nums[r] % 2);
11 while (count > goal) {
12 count -= (nums[l] % 2);
13 l++;
14 }
15 ans += (r - l + 1);
16 }
17 return ans;
18}
19
20int numberOfSubarrays(const vector<int>& nums, int k) {
21 return atMost(nums, k) - atMost(nums, k - 1);
22}
23
24int main() {
25 vector<int> nums = {1, 1, 2, 1, 1};
26 int k = 3;
27 int result = numberOfSubarrays(nums, k);
28 cout << "Output: " << result << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N) — Two passes through the array using sliding window; both left and right pointers move at most N times in each pass: O(2N) = O(N).
  • Space complexity: O(1) — Only constant extra variables (l, r, count, ans) used.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute ForceO(N^2)O(1)Iterate through all pairs (i, j), count odds in range.Redundant counting across overlapping subarrays.
2.Better — Prefix Frequency ArrayO(N)O(N)Store count of prefix sums in frequency array. Add count[prefixSum - k] at each step.Memory allocation for frequency table.
3.Optimal — Sliding Window AtMost(k) - AtMost(k-1)OptimalO(N)O(1)Compute atMost(k) - atMost(k-1) using two-pointer sliding window.None; industry-standard optimal solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • No odd numbers in array: nums = [2, 4, 6], k = 1 -> returns 0.
  • Array where every element is odd: nums = [1, 3, 5], k = 2 -> [1, 3] and [3, 5], returns 2.
  • k equals total number of odds in entire array.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Count Number of Nice Subarrays?

2.Why is the brute force approach suboptimal for large inputs in Count Number of Nice Subarrays?

3.Which data structure or technique enables the optimal solution for Count Number of Nice Subarrays?

Back to DSA Sheet