Count Number of Nice Subarrays

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 u…


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


Print Share Comment Cite Upload Translate Updates
APA

ZeeshanAli-0704 | Sciencx (2024-06-22T04:28:12+00:00) Count Number of Nice Subarrays. Retrieved from https://www.scien.cx/2024/06/22/count-number-of-nice-subarrays/

MLA
" » Count Number of Nice Subarrays." ZeeshanAli-0704 | Sciencx - Saturday June 22, 2024, https://www.scien.cx/2024/06/22/count-number-of-nice-subarrays/
HARVARD
ZeeshanAli-0704 | Sciencx Saturday June 22, 2024 » Count Number of Nice Subarrays., viewed ,<https://www.scien.cx/2024/06/22/count-number-of-nice-subarrays/>
VANCOUVER
ZeeshanAli-0704 | Sciencx - » Count Number of Nice Subarrays. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/06/22/count-number-of-nice-subarrays/
CHICAGO
" » Count Number of Nice Subarrays." ZeeshanAli-0704 | Sciencx - Accessed . https://www.scien.cx/2024/06/22/count-number-of-nice-subarrays/
IEEE
" » Count Number of Nice Subarrays." ZeeshanAli-0704 | Sciencx [Online]. Available: https://www.scien.cx/2024/06/22/count-number-of-nice-subarrays/. [Accessed: ]
rf:citation
» Count Number of Nice Subarrays | ZeeshanAli-0704 | Sciencx | https://www.scien.cx/2024/06/22/count-number-of-nice-subarrays/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts