Count Number of Nice Subarrays - Sliding Window - Visualization - Visualization

Sliding Window & Two Pointer Problems

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given an integer array nums and an integer k, return the number of nice subarrays.

A nice subarray is a contiguous subarray that contains exactly k odd numbers.

Example:
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The nice subarrays are [1,1,2,1] and [1,2,1,1].

Examples❯

nums k Output Description
[1, 1, 2, 1, 1] 3 2 Two subarrays with exactly 3 odd numbers: [1,1,2,1] and [1,2,1,1]
[2, 4, 6] 1 0 No odd numbers in array; zero subarrays with 1 odd number
[2, 2, 2, 1, 2, 2, 1, 2, 2, 2] 2 16 Several subarrays containing exactly 2 odd numbers
[1, 3, 5] 1 3 Each single element subarray [1], [3], [5] has exactly one odd number
[1, 2, 1, 2, 1] 2 4 Four subarrays with exactly 2 odd numbers
[1, 2, 3, 4, 5] 0 3 Three subarrays with zero odd numbers: [2], [4], [2,4]
[] 1 0 Empty array; no subarrays possible, hence output is 0
[2] 0 1 Single even element is a valid subarray with 0 odd numbers
[1] 0 0 Single odd element cannot form a subarray with 0 odd numbers
[1] 1 1 Single element [1] is a valid subarray with exactly 1 odd number

Solution❯

Understanding the Problem

We are given an integer array nums and an integer k. Our goal is to count how many contiguous subarrays (or continuous slices of the array) have exactly k odd numbers.

These subarrays are called nice subarrays.

For example:

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

Nice subarrays with exactly 3 odd numbers: [1, 1, 2, 1] and [1, 2, 1, 1].

Step-by-Step Solution with Example

Step 1: Reframe the Problem

Instead of directly counting subarrays with exactly k odd numbers, we count:

  • Subarrays with at most k odd numbers
  • Subarrays with at most k-1 odd numbers

The number of subarrays with exactly k odd numbers is the difference:

exactlyK(k) = atMost(k) - atMost(k - 1)

Step 2: Understand the Helper Function atMost(k)

This function counts how many subarrays have at most k odd numbers using the sliding window approach.

  • We use two pointers: left and right.
  • We move the right pointer one step at a time and track the number of odd numbers in the current window.
  • If the count of odd numbers exceeds k, we move the left pointer to shrink the window.
  • At every step, we add right - left + 1 to the result because that’s how many valid subarrays end at right.

Step 3: Walk Through the Example [1, 1, 2, 1, 1] with k = 3

Let’s compute atMost(3) first:

  • right = 0, num = 1 → oddCount = 1, subarrays = 1
  • right = 1, num = 1 → oddCount = 2, subarrays = 3
  • right = 2, num = 2 → even, oddCount = 2, subarrays = 6
  • right = 3, num = 1 → oddCount = 3, subarrays = 10
  • right = 4, num = 1 → oddCount = 4 → exceed k → move left to reduce oddCount = 3 → subarrays = 14

So, atMost(3) = 14

Now compute atMost(2) using similar steps and you’ll get 12.

Final count = 14 - 12 = 2, which matches our expected output.

Step 4: Implement in Code


def numberOfSubarrays(nums, k):
    def atMost(k):
        left = 0
        count = 0
        oddCount = 0

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

    return atMost(k) - atMost(k - 1)

Edge Cases

  • All even numbers: If nums contains no odd numbers, the answer will be 0 unless k == 0.
  • All odd numbers: Can form many nice subarrays. Be careful with boundaries and window resizing.
  • Empty array: Should return 0 safely.
  • k greater than total odd numbers: No subarray can satisfy, so answer is 0.

Final Thoughts

This problem becomes manageable by converting the exact count question into a more flexible "at most" count using the sliding window technique. It’s an elegant way to reduce complexity and helps you gain insight into how prefix counts and window shrinking work together.

By following the logic carefully and considering all edge cases, beginners can confidently solve such array problems using two-pointer strategies.

Algorithm Steps❯

  1. Define a helper function atMost(k) that returns the count of subarrays with at most k odd numbers.
  2. Use a sliding window with two pointers left and right.
  3. Keep a counter oddCount to track the number of odd numbers in the current window.
  4. Initialize a result counter res = 0.
  5. Traverse the array with the right pointer:
  6. → If nums[right] is odd, decrement k (or increment oddCount).
  7. → While oddCount > k, move the left pointer forward and adjust oddCount if needed.
  8. → For each right, add (right - left + 1) to the result, which represents subarrays ending at right.
  9. Finally, return atMost(k) - atMost(k-1) to get the count of subarrays with exactly k odd numbers.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int atMost(int* nums, int numsSize, int k) {
    int left = 0, right = 0, count = 0, oddCount = 0;
    for (right = 0; right < numsSize; right++) {
        if (nums[right] % 2 != 0) oddCount++;
        while (oddCount > k) {
            if (nums[left] % 2 != 0) oddCount--;
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

int numberOfNiceSubarrays(int* nums, int numsSize, int k) {
    return atMost(nums, numsSize, k) - atMost(nums, numsSize, k - 1);
}

int main() {
    int nums[] = {1,1,2,1,1};
    int k = 3;
    int size = sizeof(nums) / sizeof(nums[0]);
    int result = numberOfNiceSubarrays(nums, size, k);
    printf("Number of nice subarrays: %d\n", result); // Output: 2
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)The algorithm processes each element of the array once using a sliding window. Even in the best case, it must scan all elements to maintain the window and count valid subarrays.
Average CaseO(n)In the average case, the algorithm maintains a window using two pointers and counts valid subarrays by scanning each element exactly once. Thus, the time complexity is linear with respect to the size of the input array.
Worst CaseO(n)Even in the worst case (e.g., every element is odd), the window still expands and contracts by moving each pointer at most n times. Hence, the total number of operations is proportional to n.

Space Complexity❯

O(1)

Explanation: The algorithm uses a constant amount of extra space for variables like left, right, oddCount, and result counters. No additional data structures are used, making the space complexity constant.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...