Count Number of Nice Subarrays

This content originally appeared on DEV Community and was authored by ZeeshanAli-0704

Let’s go through the code step by step to understand how it calculates the number of “nice” subarrays, where a “nice” subarray contains exactly k odd numbers.

Count Number of Nice Subarrays

Code Explanation

The function numberOfSubarrays uses a sliding window approach to count subarrays with exactly k odd numbers.

Initial State

• countOdd = 0: Keeps track of the number of odd numbers in the current window.
• l = 0: The left pointer of the sliding window.
• m = 0: A pointer to help count subarrays starting from l.
• result = 0: Accumulates the total number of nice subarrays found.

Iteration Over the Array

for (let r = 0; r < nums.length; r++) {
    if (nums[r] % 2 !== 0) {
        countOdd++;
    }

• The loop iterates through the array with the right pointer r.
• For each element nums[r], if it is odd, countOdd is incremented.

Adjusting the Left Pointer (l)

while (countOdd > k) {
    if (nums[l] % 2 !== 0) {
        countOdd--;
    }
    l++;
    m = l;
}

• When countOdd exceeds k, the left pointer l is moved to the right until countOdd is equal to k.
• If the element at l is odd, decrement countOdd.
• Move l to the right and set m to l.

Counting Valid Subarrays

if (countOdd === k) {
    while (nums[m] % 2 === 0) {
        m++;
    }
    result += (m - l) + 1;
}

• When countOdd is equal to k, count the number of valid subarrays.
• Move pointer m to the right as long as the elements are even.
• The number of valid subarrays ending at r is (m - l) + 1.
• Add this count to result.

Return the Result

return result;

• Return the total count of nice subarrays.

Example Walkthrough

Let’s consider the array nums = [2, 2, 2, 1, 2, 2, 1, 2, 2, 2] with k = 2.

Initial State

• countOdd = 0
• l = 0
• m = 0
• result = 0

Iteration Over nums

Iteration 1 to 3 (r = 0 to 2)

• All elements are even, countOdd remains 0.

Iteration 4 (r = 3)

• nums[3] = 1, countOdd = 1.

Iteration 5 to 6 (r = 4 to 5)

• All elements are even, countOdd remains 1.

Iteration 7 (r = 6)

• nums[6] = 1, countOdd = 2.
• countOdd is now equal to k.
• Move m to 6 (where nums[m] = 1).
• result += (6 - 3) + 1 = 4.

Iteration 8 (r = 7)

• nums[7] = 2, countOdd remains 2.
• m remains 6.
• result += (6 - 3) + 1 = 4.
• result is now 8.

Iteration 9 (r = 8)

• nums[8] = 2, countOdd remains 2.
• m remains 6.
• result += (6 - 3) + 1 = 4.
• result is now 12.

Iteration 10 (r = 9)

• nums[9] = 2, countOdd remains 2.
• m remains 6.
• result += (6 - 3) + 1 = 4.
• result is now 16.

Final Calculation

Return result, which is 16.

Summary

The algorithm effectively uses two pointers to maintain a sliding window and count subarrays with exactly k odd numbers. It correctly counts all valid subarrays ending at each position r, ensuring efficient and accurate calculation.

var numberOfSubarrays = function (nums, k) {
    let countOdd = 0;
    let l = 0;
    let m = 0;
    let result = 0;

    for (let r = 0; r < nums.length; r++) {
        if (nums[r] % 2 !== 0) {
            countOdd++;
        }

        while (countOdd > k) {
            if (nums[l] % 2 !== 0) {
                countOdd--;
            }
            l++;
            m = l;
        }
        if (countOdd === k) {
            while (nums[m] % 2 == 0) {
                m++
            }

            result += (m - l) + 1;
        }

    }
    return result;
};

This content originally appeared on DEV Community and was authored by ZeeshanAli-0704