Count Number of Nice Subarrays - Practice Coding Problems

Count Number of Nice Subarrays - Problem

Array Hash Table Math Sliding Window Prefix Sum Medium

Given an array of integers nums and an integer k, a continuous subarray is called nice if there are exactly k odd numbers in it.

Return the number of nice sub-arrays.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: The only nice subarrays are [1,1,2,1] and [1,2,1,1], each containing exactly 3 odd numbers.

Example 2 — Smaller k

$ Input: nums = [2,4,6], k = 1

› Output: 0

💡 Note: All numbers are even, so no subarray can have exactly 1 odd number.

Example 3 — Single Element

$ Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2

› Output: 16

💡 Note: Multiple subarrays contain exactly 2 odd numbers, including various combinations around the two odd numbers at positions 3 and 6.

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
1 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array with mixed odd/even numbers and target k

Process

Find all continuous subarrays with exactly k odds

Output

Count of valid subarrays

Key Takeaway

🎯 Key Insight: Transform the counting problem by focusing on odd/even patterns rather than actual values

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is to transform the problem by treating odd numbers as 1 and even numbers as 0, then use either prefix sums with hash map or sliding window technique. The sliding window approach using atMost(k) - atMost(k-1) is most intuitive. Time: O(n), Space: O(1) for sliding window or O(n) for prefix sum.

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum with Hash Map	O(n)	O(n)	Transform problem using prefix sums of odd counts
Sliding Window	O(n)	O(1)	Use variable sliding window with helper function
Brute Force	O(n³)	O(1)	Check every possible subarray and count odd numbers

Prefix Sum with Hash Map — Algorithm Steps

Transform array: odd→1, even→0
Calculate prefix sums
Use hash map to count occurrences
For each position, add count of (prefixSum - k)

Visualization

Tap to expand

Step-by-Step Walkthrough

Transform

Convert odds to 1, evens to 0

Prefix Sums

Calculate running sum of 1s and 0s

Count Differences

Find pairs where difference equals k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 50000

int solution(int* nums, int numsSize, int k) {
    int count = 0;
    int prefixSum = 0;
    int prefixCount[MAXN + 1] = {0};
    prefixCount[0] = 1;
    
    for (int i = 0; i < numsSize; i++) {
        prefixSum += nums[i] % 2;
        if (prefixSum >= k) {
            count += prefixCount[prefixSum - k];
        }
        prefixCount[prefixSum]++;
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array with constant time hash map operations

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n prefix sum counts

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler