Count Number of Nice Subarrays (K Odd Numbers)

🎯

Count Number of Nice Subarrays (K Odd Numbers)

mediumSLIDING_WINDOWAmazonGoogle

Imagine you are analyzing a stream of numbers and want to find how many continuous segments contain exactly K odd numbers - like counting special patterns in a data stream.

💡 This problem is about counting subarrays with a specific property (exactly K odd numbers). Beginners often struggle because naive solutions try to check every subarray, which is too slow. Understanding how to efficiently track and count these subarrays using sliding window techniques is key.

📋

Problem Statement

Given an integer array nums and an integer k, return the number of nice subarrays. A nice subarray is defined as a contiguous subarray that contains exactly k odd numbers.

1 ≤ nums.length ≤ 10^51 ≤ nums[i] ≤ 10^51 ≤ k ≤ nums.length

💡

Example

Input"nums = [1,1,2,1,1], k = 3"

Output2

The subarrays [1,1,2,1] and [1,2,1,1] each contain exactly 3 odd numbers.

Input"nums = [2,4,6], k = 1"

Output0

No subarray contains any odd number, so result is 0.

Input"nums = [2,2,2,1,2,2,1,2,2,2], k = 2"

Output16

There are 16 subarrays containing exactly 2 odd numbers.

• All elements are even → output should be 0
• k equals the length of the array → only one subarray possible
• Array with alternating odd and even numbers → multiple overlapping subarrays
• Array with all odd numbers → count subarrays with exactly k odds

⚠️

Common Mistakes

Not breaking early when odd count exceeds k in brute force

Unnecessary computations leading to TLE

✅ Add a break when odd_count > k inside inner loop

Off-by-one errors when calculating gaps in prefix indices approach

Incorrect count of subarrays, wrong output

✅ Use sentinel indices and carefully compute gap lengths

Incorrectly counting subarrays with at most k odds in sliding window

Wrong final answer due to miscounting

✅ Ensure to add (right - left + 1) to count at each step

Not handling k=0 or k=1 edge cases properly

Runtime errors or wrong results

✅ Check for k-1 >= 0 before calling countAtMost with k-1

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by explicitly checking every possible subarray. Though inefficient, it builds intuition about what defines a 'nice' subarray.

Intuition

Check every subarray and count how many odd numbers it contains. If the count equals k, increment the result.

Algorithm

1. Initialize a result counter to 0.
2. Use two nested loops to consider every subarray.
3. For each subarray, count the number of odd numbers.
4. If the count equals k, increment the result.

💡 The nested loops make it clear what we are counting, but the repeated counting of odds in overlapping subarrays is inefficient.

</>

Code

def countNiceSubarrays(nums, k):
    n = len(nums)
    result = 0
    for start in range(n):
        odd_count = 0
        for end in range(start, n):
            if nums[end] % 2 == 1:
                odd_count += 1
            if odd_count == k:
                result += 1
            elif odd_count > k:
                break
    return result

# Driver code
if __name__ == '__main__':
    print(countNiceSubarrays([1,1,2,1,1], 3))  # Output: 2

Line Notes

for start in range(n):Outer loop picks the start index of subarray

odd_count = 0Reset odd count for each new start

for end in range(start, n):Inner loop picks the end index of subarray

if nums[end] % 2 == 1:Check if current element is odd to update count

if odd_count == k:If exactly k odds, increment result

elif odd_count > k:No need to continue if odds exceed k

public class Solution {
    public int countNiceSubarrays(int[] nums, int k) {
        int n = nums.length;
        int result = 0;
        for (int start = 0; start < n; start++) {
            int oddCount = 0;
            for (int end = start; end < n; end++) {
                if (nums[end] % 2 == 1) {
                    oddCount++;
                }
                if (oddCount == k) {
                    result++;
                } else if (oddCount > k) {
                    break;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countNiceSubarrays(new int[]{1,1,2,1,1}, 3)); // Output: 2
    }
}

Line Notes

for (int start = 0; start < n; start++) {Outer loop selects subarray start

int oddCount = 0;Reset odd count for each start

for (int end = start; end < n; end++) {Inner loop selects subarray end

if (nums[end] % 2 == 1) {Check if current element is odd

if (oddCount == k) {Increment result when exactly k odds found

else if (oddCount > k) {Stop early if odds exceed k

#include <iostream>
#include <vector>
using namespace std;

int countNiceSubarrays(vector<int>& nums, int k) {
    int n = nums.size();
    int result = 0;
    for (int start = 0; start < n; start++) {
        int oddCount = 0;
        for (int end = start; end < n; end++) {
            if (nums[end] % 2 == 1) {
                oddCount++;
            }
            if (oddCount == k) {
                result++;
            } else if (oddCount > k) {
                break;
            }
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1,1,2,1,1};
    cout << countNiceSubarrays(nums, 3) << endl; // Output: 2
    return 0;
}

Line Notes

for (int start = 0; start < n; start++) {Outer loop for subarray start index

int oddCount = 0;Reset odd count for each new start

for (int end = start; end < n; end++) {Inner loop for subarray end index

if (nums[end] % 2 == 1) {Check if current element is odd

if (oddCount == k) {Increment result when exactly k odds found

else if (oddCount > k) {Break early to avoid unnecessary checks

function countNiceSubarrays(nums, k) {
    let n = nums.length;
    let result = 0;
    for (let start = 0; start < n; start++) {
        let oddCount = 0;
        for (let end = start; end < n; end++) {
            if (nums[end] % 2 === 1) {
                oddCount++;
            }
            if (oddCount === k) {
                result++;
            } else if (oddCount > k) {
                break;
            }
        }
    }
    return result;
}

// Test
console.log(countNiceSubarrays([1,1,2,1,1], 3)); // Output: 2

Line Notes

for (let start = 0; start < n; start++) {Outer loop picks subarray start

let oddCount = 0;Reset odd count for each start

for (let end = start; end < n; end++) {Inner loop picks subarray end

if (nums[end] % 2 === 1) {Check if current element is odd

if (oddCount === k) {Increment result when exactly k odds found

else if (oddCount > k) {Stop inner loop early if odds exceed k

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, so O(n^2). No extra space besides counters.

💡 For n=1000, this means about 1,000,000 operations, which is slow but still feasible for small inputs.

Interview Verdict: TLE for large inputs

This approach is too slow for large arrays but is useful to understand the problem and correctness.

🧠

Prefix Indices of Odd Numbers + Counting

💡 This approach uses the positions of odd numbers to count subarrays efficiently, avoiding checking every subarray explicitly.

Intuition

Record indices of all odd numbers, then count how many subarrays have exactly k odd numbers by looking at gaps between these indices.

Algorithm

1. Create a list of indices where nums[i] is odd, add sentinel indices at start and end.
2. For each group of k consecutive odd indices, calculate the number of subarrays by multiplying the gap sizes before and after.
3. Sum these counts to get the total number of nice subarrays.

💡 This method counts subarrays indirectly by counting how many start and end positions can form valid subarrays around odd numbers.

</>

Code

def countNiceSubarrays(nums, k):
    odd_indices = [-1]
    for i, num in enumerate(nums):
        if num % 2 == 1:
            odd_indices.append(i)
    odd_indices.append(len(nums))

    result = 0
    for i in range(1, len(odd_indices) - k):
        left_count = odd_indices[i] - odd_indices[i - 1]
        right_count = odd_indices[i + k] - odd_indices[i + k - 1]
        result += left_count * right_count
    return result

# Driver code
if __name__ == '__main__':
    print(countNiceSubarrays([1,1,2,1,1], 3))  # Output: 2

Line Notes

odd_indices = [-1]Add sentinel before start to handle subarrays starting at index 0

if num % 2 == 1:Record index of each odd number

odd_indices.append(len(nums))Add sentinel after end to handle subarrays ending at last index

left_count = odd_indices[i] - odd_indices[i - 1]Count of even numbers (or gap) before current odd

right_count = odd_indices[i + k] - odd_indices[i + k - 1]Count of even numbers after the kth odd

result += left_count * right_countNumber of subarrays formed by combining left and right gaps

import java.util.*;

public class Solution {
    public int countNiceSubarrays(int[] nums, int k) {
        List<Integer> oddIndices = new ArrayList<>();
        oddIndices.add(-1);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 1) {
                oddIndices.add(i);
            }
        }
        oddIndices.add(nums.length);

        int result = 0;
        for (int i = 1; i + k < oddIndices.size(); i++) {
            int leftCount = oddIndices.get(i) - oddIndices.get(i - 1);
            int rightCount = oddIndices.get(i + k) - oddIndices.get(i + k - 1);
            result += leftCount * rightCount;
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countNiceSubarrays(new int[]{1,1,2,1,1}, 3)); // Output: 2
    }
}

Line Notes

oddIndices.add(-1);Sentinel before start to handle subarrays starting at index 0

if (nums[i] % 2 == 1) {Record index of each odd number

oddIndices.add(nums.length);Sentinel after end to handle subarrays ending at last index

int leftCount = oddIndices.get(i) - oddIndices.get(i - 1);Count gap before current odd

int rightCount = oddIndices.get(i + k) - oddIndices.get(i + k - 1);Count gap after kth odd

result += leftCount * rightCount;Count subarrays formed by combining gaps

#include <iostream>
#include <vector>
using namespace std;

int countNiceSubarrays(vector<int>& nums, int k) {
    vector<int> oddIndices = {-1};
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] % 2 == 1) {
            oddIndices.push_back(i);
        }
    }
    oddIndices.push_back(nums.size());

    int result = 0;
    for (int i = 1; i + k < oddIndices.size(); i++) {
        int leftCount = oddIndices[i] - oddIndices[i - 1];
        int rightCount = oddIndices[i + k] - oddIndices[i + k - 1];
        result += leftCount * rightCount;
    }
    return result;
}

int main() {
    vector<int> nums = {1,1,2,1,1};
    cout << countNiceSubarrays(nums, 3) << endl; // Output: 2
    return 0;
}

Line Notes

vector<int> oddIndices = {-1};Sentinel before start for subarray counting

if (nums[i] % 2 == 1) {Record index of odd numbers

oddIndices.push_back(nums.size());Sentinel after end for subarray counting

int leftCount = oddIndices[i] - oddIndices[i - 1];Gap before current odd

int rightCount = oddIndices[i + k] - oddIndices[i + k - 1];Gap after kth odd

result += leftCount * rightCount;Count subarrays by multiplying gap sizes

function countNiceSubarrays(nums, k) {
    const oddIndices = [-1];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 === 1) {
            oddIndices.push(i);
        }
    }
    oddIndices.push(nums.length);

    let result = 0;
    for (let i = 1; i + k < oddIndices.length; i++) {
        const leftCount = oddIndices[i] - oddIndices[i - 1];
        const rightCount = oddIndices[i + k] - oddIndices[i + k - 1];
        result += leftCount * rightCount;
    }
    return result;
}

// Test
console.log(countNiceSubarrays([1,1,2,1,1], 3)); // Output: 2

Line Notes

const oddIndices = [-1];Sentinel before start to handle subarrays starting at 0

if (nums[i] % 2 === 1) {Record index of odd numbers

oddIndices.push(nums.length);Sentinel after end to handle subarrays ending at last index

const leftCount = oddIndices[i] - oddIndices[i - 1];Gap before current odd

const rightCount = oddIndices[i + k] - oddIndices[i + k - 1];Gap after kth odd

result += leftCount * rightCount;Count subarrays by multiplying gap sizes

⏱

Complexity

TimeO(n)

SpaceO(n)

We scan the array once to record odd indices, then iterate over them once. Space is used to store odd indices.

💡 For n=100000, this approach is efficient and fast enough for large inputs.

Interview Verdict: Accepted

This approach is efficient and suitable for large inputs, leveraging problem structure.

🧠

Sliding Window with Two Pointers

💡 This approach uses two sliding windows to count subarrays with exactly k odd numbers by counting subarrays with at most k and at most k-1 odd numbers.

Intuition

Number of subarrays with exactly k odd numbers = number with at most k odds - number with at most k-1 odds. Use two pointers to count subarrays with at most k odds efficiently.

Algorithm

1. Define a helper function to count subarrays with at most k odd numbers.
2. Use two pointers to expand and shrink the window while counting valid subarrays.
3. Calculate result as count(at most k) - count(at most k-1).

💡 This method cleverly uses the difference of counts to get exact subarray counts without enumerating all subarrays.

</>

Code

def countAtMost(nums, k):
    count = 0
    left = 0
    odd_count = 0
    for right in range(len(nums)):
        if nums[right] % 2 == 1:
            odd_count += 1
        while odd_count > k:
            if nums[left] % 2 == 1:
                odd_count -= 1
            left += 1
        count += right - left + 1
    return count

def countNiceSubarrays(nums, k):
    return countAtMost(nums, k) - countAtMost(nums, k - 1)

# Driver code
if __name__ == '__main__':
    print(countNiceSubarrays([1,1,2,1,1], 3))  # Output: 2

Line Notes

if nums[right] % 2 == 1:Increment odd count when odd found

while odd_count > k:Shrink window from left if too many odds

count += right - left + 1Add number of valid subarrays ending at right

return countAtMost(nums, k) - countAtMost(nums, k - 1)Difference gives exact count of subarrays with k odds

public class Solution {
    private int countAtMost(int[] nums, int k) {
        int count = 0, left = 0, oddCount = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] % 2 == 1) {
                oddCount++;
            }
            while (oddCount > k) {
                if (nums[left] % 2 == 1) {
                    oddCount--;
                }
                left++;
            }
            count += right - left + 1;
        }
        return count;
    }

    public int countNiceSubarrays(int[] nums, int k) {
        return countAtMost(nums, k) - countAtMost(nums, k - 1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countNiceSubarrays(new int[]{1,1,2,1,1}, 3)); // Output: 2
    }
}

Line Notes

if (nums[right] % 2 == 1) {Increment odd count when odd found

while (oddCount > k) {Shrink window from left if too many odds

count += right - left + 1;Add count of valid subarrays ending at right

return countAtMost(nums, k) - countAtMost(nums, k - 1);Difference gives exact count of subarrays with k odds

#include <iostream>
#include <vector>
using namespace std;

int countAtMost(vector<int>& nums, int k) {
    int count = 0, left = 0, oddCount = 0;
    for (int right = 0; right < nums.size(); right++) {
        if (nums[right] % 2 == 1) {
            oddCount++;
        }
        while (oddCount > k) {
            if (nums[left] % 2 == 1) {
                oddCount--;
            }
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

int countNiceSubarrays(vector<int>& nums, int k) {
    return countAtMost(nums, k) - countAtMost(nums, k - 1);
}

int main() {
    vector<int> nums = {1,1,2,1,1};
    cout << countNiceSubarrays(nums, 3) << endl; // Output: 2
    return 0;
}

Line Notes

if (nums[right] % 2 == 1) {Increment odd count when odd found

while (oddCount > k) {Shrink window from left if too many odds

count += right - left + 1;Add count of valid subarrays ending at right

return countAtMost(nums, k) - countAtMost(nums, k - 1);Difference gives exact count of subarrays with k odds

function countAtMost(nums, k) {
    let count = 0, left = 0, oddCount = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] % 2 === 1) {
            oddCount++;
        }
        while (oddCount > k) {
            if (nums[left] % 2 === 1) {
                oddCount--;
            }
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

function countNiceSubarrays(nums, k) {
    return countAtMost(nums, k) - countAtMost(nums, k - 1);
}

// Test
console.log(countNiceSubarrays([1,1,2,1,1], 3)); // Output: 2

Line Notes

if (nums[right] % 2 === 1) {Increment odd count when odd found

while (oddCount > k) {Shrink window from left if too many odds

count += right - left + 1;Add count of valid subarrays ending at right

return countAtMost(nums, k) - countAtMost(nums, k - 1);Difference gives exact count of subarrays with k odds

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most twice by the two pointers, so linear time. Only constant extra space used.

💡 For n=100000, this approach is very efficient and uses minimal memory.

Interview Verdict: Accepted

This is the most intuitive and efficient approach for this problem in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the sliding window approach is usually best due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code for large inputs
2. Prefix Indices Counting	O(n)	O(n)	No	N/A	Good to mention as a clever counting trick
3. Sliding Window Two Pointers	O(n)	O(1)	No	N/A	Best to code in interviews for clarity and efficiency

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the prefix odd indices counting method as an optimization.Step 4: Present the sliding window two-pointer approach as the optimal solution.Step 5: Code the sliding window approach and test with examples.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Coding: 10min → Testing & optimization: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to identify the pattern, optimize from brute force to linear time, and correctly implement sliding window logic.

Common Follow-ups

• What if we want subarrays with at most k odd numbers? → Use the countAtMost function directly.
• How to handle very large arrays efficiently? → Use O(n) sliding window approach.
• Can this approach be adapted for even numbers or other conditions? → Yes, by changing the condition checked.
• What if we want subarrays with exactly k even numbers? → Similar logic applies by tracking even numbers.

💡 These follow-ups test your flexibility in adapting the solution and understanding of sliding window variations.

🔍

Pattern Recognition

When to Use

1) Asked to count subarrays with exact count of a property; 2) Property can be tracked incrementally; 3) Constraints allow linear or near-linear solution; 4) Problem hints at sliding window or prefix sums.

Signature Phrases

'exactly k odd numbers''count number of subarrays''contiguous subarray with k odds'

NOT This Pattern When

Problems asking for maximum/minimum subarray sums or fixed-size windows are different patterns.

Similar Problems

Subarrays with K Different Integers - similar counting with constraintsNumber of Subarrays with Bounded Maximum - sliding window with bounds

Practice

1. Consider the following Python code implementing the optimal sliding window approach for the character replacement problem. What is the returned value when the input is s = "AABA" and k = 1?

easy

A. 4

B. 3

C. 2

D. 1

Solution

1. Step 1: Trace window expansion and frequency updates

   Index 0: freq[A]=1, max_count=1, window=[0,0], max_len=1 Index 1: freq[A]=2, max_count=2, window=[0,1], max_len=2 Index 2: freq[B]=1, max_count=2, window=[0,2], window size=3, replacements needed=1 ≤ k=1, max_len=3 Index 3: freq[A]=3, max_count=3, window=[0,3], window size=4, replacements needed=1 ≤ k=1, max_len=4

2. Step 2: Check while condition and final max_len

   At index 3, window size 4 with max_count 3 means 1 replacement needed, which is allowed. So max_len updates to 4. The function returns 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Window expands fully with one replacement allowed [OK]

Hint: Max length includes full string if replacements ≤ k [OK]

Common Mistakes:

• Off-by-one error in window size calculation
• Not updating max_count correctly
• Misunderstanding when to shrink window

2. Consider the following code snippet implementing the optimal sliding window approach to check if s2 contains a permutation of s1. Given s1 = "ab" and s2 = "eidbaooo", what is the return value of the function?

easy

A. True

B. Raises an IndexError

C. False

D. Returns None

Solution

1. Step 1: Trace window expansion and counts

   For s1 = "ab", count array has counts for 'a' and 'b'. Sliding window moves over s2 = "eidbaooo". When window covers substring "ba" starting at index 3, window_count matches count, so formed == required.

2. Step 2: Confirm return value

   At this point, function returns True because a permutation of s1 is found in s2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Substring "ba" is a permutation of "ab" [OK]

Hint: Check substring "ba" matches "ab" permutation [OK]

Common Mistakes:

• Off-by-one errors in window size
• Forgetting to return True when formed == required

3. What is the time complexity of the optimal sliding window solution for the Longest Repeating Character Replacement problem, assuming the input string length is n and the character set size is fixed (e.g., 26 uppercase letters)?

medium

A. O(n) because each character is visited at most twice by left and right pointers

B. O(n^2) because the window can shrink and expand multiple times

C. O(n * k) because the inner loop depends on the number of allowed replacements

D. O(n) but with O(n) auxiliary space due to frequency map storage

Solution

1. Step 1: Analyze pointer movements

   Right pointer moves from 0 to n-1 once. Left pointer only moves forward when window is invalid, also at most n times.

2. Step 2: Consider frequency array and fixed character set

   Frequency array is fixed size (26), so updates are O(1). No nested loops over n inside main loop.

3. Step 3: Analyze space complexity

   The frequency array uses O(1) space since the character set is fixed, not O(n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two-pointer linear scan with fixed-size frequency array [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Thinking k affects inner loop complexity
• Confusing frequency map space with time complexity

4. What is the time complexity of the optimized sliding window algorithm that uses a hash map to track the last seen indices of characters for finding the longest substring without repeating characters?

medium

A. O(n) because each character is visited at most twice by the right and left pointers

B. O(n^2) because each character may cause the left pointer to move multiple times

C. O(n log n) due to hash map operations on each character

D. O(n * m) where m is the size of the character set

Solution

1. Step 1: Analyze pointer movements

   Right pointer moves forward once per character. Left pointer only moves forward when duplicates are found, never backward. Each character is visited at most twice.

2. Step 2: Consider hash map operations

   Hash map lookups and updates are O(1) average. Thus total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window with hash map -> linear time [OK]

Hint: Each character visited max twice -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing hash map average with worst-case

5. Suppose the sliding window maximum problem is modified so that elements can be reused multiple times (i.e., the window can slide but elements may appear multiple times in the output). Which of the following statements about the monotonic deque approach is true?

hard

A. The monotonic deque approach fails because it assumes each element appears only once; a max-heap is required instead.

B. The monotonic deque approach must be modified to track counts of elements to handle reuse correctly.

C. The monotonic deque approach works without any changes since it only depends on indices.

D. The problem reduces to a different pattern; monotonic deque is not applicable and a segment tree is needed.

Solution

1. Step 1: Understand the reuse modification

   Allowing elements to be reused means the same element can contribute multiple times as the window slides, potentially overlapping.

2. Step 2: Analyze monotonic deque assumptions

   The original deque stores indices assuming each element appears once per position. To handle reuse, counts or frequency tracking is needed to maintain correctness.

3. Step 3: Evaluate other options

   Monotonic deque without modification fails; max-heap alone is inefficient; segment tree is overkill for this variant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Tracking counts allows correct max maintenance with reuse [OK]

Hint: Reuse breaks unique index assumption; track counts to fix [OK]

Common Mistakes:

• Assuming no changes needed for reuse
• Switching to max-heap without efficiency gain
• Thinking monotonic deque is inapplicable