L10. Count number of Nice Subarrays | Two Pointers and Sliding Window

This chapter explores how to identify underlying patterns in seemingly new problems by transforming them into familiar ones. We will solve the problem of counting "nice subarrays" where the count of odd numbers equals a given integer $K$, leveraging our prior knowledge of binary subarray sum problems.

1. Problem Statement: Count Number of Nice Subarrays

We are given an array of integers, nums, and an integer value, $K$. Our task is to count the total number of "nice subarrays" within nums.

• Subarray: A contiguous portion of the array.
• Nice Subarray Definition: A contiguous portion of the array where the count of odd integers is exactly equal to $K$.

Example Breakdown

Consider an array with mixed odd and even numbers, where $K = 3$:

nums = [1, 1, 2, 1, 1], K = 3

• If we examine a subarray containing elements with two odd numbers and one even number, it cannot be counted.
• If we examine a contiguous portion containing exactly three odd numbers and any number of evens (such as three 1s and one 2), it is a valid nice subarray.

Our objective is to return the total count of such valid contiguous subarrays.

2. Recognizing the Prerequisite Pattern

Before diving into a custom solution, we must recognize that this problem is a direct linguistic variation of a well-known precursor: Binary Subarrays with Sum (where an array consists only of 1s and 0s, and we count subarrays whose sum equals a target goal).

Problem Setter's Tactic:
Original Problem: Count binary subarrays with sum == goal
Twisted Problem:   Count subarrays with exact count of odd numbers == K

By connecting the two problems, we realize we do not need to invent a brand-new algorithm. We can reuse the exact same mental model and sliding window / prefix sum technique by simply transforming the input data stream.

3. The Core Mental Model: Transforming Odds and Evens to Binary

How do we convert an array containing arbitrary integers into a binary array of 1s and 0s?

Real-Life Analogy & Mapping Rule

Imagine a security checkpoint where we only care whether a person is wearing a red hat (odd number) or a blue hat (even number). We don't care about their height, age, or clothing brand—just the hat color.

We can map every number in our array using the modulo operator (% 2):

• If a number is odd, treat it as 1.
• If a number is even, treat it as 0.

Original Array: [ 1,   1,   2,   1,   1 ]
                 |    |    |    |    |
Transform (%2):  v    v    v    v    v
Binary Array:   [ 1,   1,   0,   1,   1 ]  with Target K = 3

Once transformed, finding subarrays with exactly $K$ odd numbers is identical to finding subarrays with a binary sum equal to $K$.

4. Naive vs. Optimal Approach

Naive Approach (Brute Force)

• Strategy: Generate every possible subarray using nested loops, count the number of odd integers in each subarray, and check if the count matches $K$.
• Time Complexity: $O(N^2)$ because there are $O(N^2)$ possible subarrays.
• Space Complexity: $O(1)$ auxiliary space.
• Limitation: Inefficient for large arrays where $N$ can be up to $10^5$.

Optimal Approach (Sliding Window / Two Pointers via At-Most Pattern)

• Strategy: Instead of searching directly for an exact count $K$, we use the classic "At Most" trick:

• Time Complexity: $O(N)$ because both the left and right pointers traverse the array linearly.
• Space Complexity: $O(1)$ as we only maintain pointers and running sums.

5. Step-by-Step Algorithm Evolution

To find subarrays where the sum equals $K$, we implement a helper function atMost(nums, K) that returns the count of subarrays with a sum less than or equal to $K$.

The atMost Sliding Window Logic

1. Initialize two pointers: left = 0, right = 0, along with sum = 0 and count = 0.
2. Expand the right pointer across the array, adding nums[right] % 2 to the sum.
3. If sum exceeds $K$, shrink the window from the left by subtracting nums[left] % 2 and incrementing left.
4. For every position of right, the number of valid subarrays ending at right with a sum $\le K$ is given by the window length: (right - left + 1).
5. Accumulate this length into the total count.

6. Code Implementation

Below is the complete implementation incorporating the odd-to-binary transformation via modulo arithmetic:

class Solution {
private:
    int atMost(vector<int>& nums, int k) {
        if (k < 0) return 0;
        
        int left = 0, right = 0;
        int sum = 0, count = 0;
        int n = nums.size();
        
        while (right < n) {
            // Transform odd to 1, even to 0 on the fly
            sum += (nums[right] % 2);
            
            // Shrink window if sum exceeds k
            while (sum > k) {
                sum -= (nums[left] % 2);
                left++;
            }
            
            // Add all valid subarrays ending at 'right'
            count += (right - left + 1);
            right++;
        }
        
        return count;
    }

public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        // Exactly(K) = AtMost(K) - AtMost(K - 1)
        return atMost(nums, k) - atMost(nums, k - 1);
    }
};

7. Complete Flow Walkthrough

Let's trace numberOfSubarrays([1, 1, 2, 1, 1], 3):

Step 1: Calculate atMost(nums, 3)
   - Window expands and contracts, counting all subarrays with <= 3 odd numbers.
   - Returns total valid subarrays for <= 3.

Step 2: Calculate atMost(nums, 2)
   - Window expands and contracts, counting all subarrays with <= 2 odd numbers.
   - Returns total valid subarrays for <= 2.

Step 3: Subtract Results
   - atMost(nums, 3) - atMost(nums, 2) = Exact subarrays with 3 odd numbers.

8. Summary and Key Takeaways

• Problem Pattern Recognition: Interviewers often disguise classic problems (like binary subarray sum) by changing the domain (e.g., counting odd integers in an array of mixed numbers).
• Data Transformation: Use modulo arithmetic (nums[i] % 2) to instantly convert arbitrary integer arrays into binary representations (1 for odd, 0 for even).
• The "At Most" Technique: To solve problems requiring an exact match ($K$), compute atMost(K) - atMost(K - 1).
• Linear Efficiency: The sliding window approach reduces time complexity from $O(N^2)$ down to $O(N)$.
• Space Optimization: Operating in-place with two pointers keeps auxiliary space complexity at $O(1)$.
• Code Reusability: Recognizing structural similarities allows you to copy-paste and adapt proven solutions rather than reinventing algorithms from scratch.