Count Number of Nice Subarrays

class Solution {
public:
    int countKSubarrays(vector<int>& nums, int k) {
        return atMostK(nums, k) - atMostK(nums, k - 1);
    }

private:
    int atMostK(vector<int>& nums, int k) {
        int count = 0, result = 0, left = 0;

        for (int right = 0; right < nums.size(); right++) {
            count += nums[right] % 2;

            while (count > k) {
                count -= nums[left] % 2;
                left++;
            }
            result += right - left + 1;
        }

        return result;
    }
};

To efficiently compute the number of "nice" subarrays with k odd numbers in C++, the provided solution implements an approach based on the difference between scenarios when there are at most k odd numbers versus at most k-1 odd numbers.

• Begin by defining the countKSubarrays function which relies on reusing the logic meant to calculate the count of subarrays with at most k odd numbers by using the helper function atMostK.
• Implement the atMostK function that will keep track of count, the number of odd numbers, result, the count of valid subarrays, and left, a pointer used for indicating the start of a window.
• Utilize a sliding window strategy:
  • Incrementally expand the window to include more elements (right pointer), updating the count of odd elements.
  • If the count exceeds k, adjust the left pointer to shrink the window until the count is appropriate again.
  • Update the count of valid subarrays for each position of the right pointer, accumulating results using the expression result += right - left + 1 to consider all subarrays ending at right.

This solution is effective in determining the number of subarrays that exactly contain k odd numbers by leveraging direct subtraction between two conditions, ensuring optimal computation and clearer results through the difference of outcomes for k and k-1. This method is highly efficient, using a sliding window approach for a time complexity of O(n) where n is the number of elements in the input array, providing a significant advantage for large datasets.

class Solution {

    public int countOddSubarrays(int[] arr, int k) {
        return countAtMost(arr, k) - countAtMost(arr, k - 1);
    }

    private int countAtMost(int[] arr, int k) {
        int countOdds = 0, result = 0, left = 0;

        for (int right = 0; right < arr.length; right++) {
            countOdds += arr[right] % 2;
            // Adjust the left index so countOdds is at most k
            while (countOdds > k) {
                countOdds -= arr[left] % 2;
                left++;
            }
            // Add the number of valid subarrays ending at right
            result += right - left + 1;
        }

        return result;
    }
}

This Java solution is designed to solve the problem of counting the number of subarrays with exactly k odd numbers. The code utilizes two major functions: countOddSubarrays and countAtMost.

• Start by analyzing the countOddSubarrays method. It leverages the operation of helper function countAtMost to find subarrays with at most k odd numbers and subarrays with at most k - 1 odd numbers. The difference between these two counts gives the exact number of subarrays with exactly k odd numbers.

• Dive deeper into the countAtMost method, which is a sliding window technique used to maintain a dynamic scope of subarray indices [left, right]. Here, countOdds keeps track of the number of odd numbers within the current window.

  • Iterate over the array using right as the moving boundary of the window.
  • Update the count of odd numbers countOdds by checking if the current element is odd.
  • If countOdds exceeds k, adjust the left point of the window to reduce the countOdds until it is at most k.
  • For each position of right, increment the result by the number of valid subarrays ending at right, which is quantified by the gap between right and left plus one (i.e., right - left + 1).

This method efficiently uses the sliding window concept, allowing the function to maintain an adaptive list of candidate subarrays while controlling the maximum allowed odd elements, resulting in an optimal calculation of the desired count of nice subarrays.

class Solution:
    def countOddSubarrays(self, array: List[int], count: int) -> int:
        return self.subarrayCountLessThanEqual(array, count) - self.subarrayCountLessThanEqual(array, count - 1)

    def subarrayCountLessThanEqual(self, array: List[int], threshold: int) -> int:
        odd_count, result, left = 0, 0, 0
        for right in range(len(array)):
            odd_count += array[right] % 2
            while odd_count > threshold:
                odd_count -= array[left] % 2
                left += 1
            result += right - left + 1
        return result

This Python code defines a method to count the number of subarrays with a given number of odd elements in a list of integers. The solution uses the two-pointer technique to efficiently find the desired subarrays.

• The countOddSubarrays function calculates the difference between:

  • The number of subarrays with odd counts less than or equal to count
  • The number of subarrays with odd counts less than count

  This difference effectively returns the number of subarrays that have exactly count odd numbers.

• The helper method subarrayCountLessThanEqual efficiently counts how many subarrays have odd counts less than or equal to a specified threshold threshold. This is accomplished by using two variables, left and right, to maintain a sliding window:

  1. Increment odd_count when an odd element is encountered as the right pointer advances.
  2. If odd_count exceeds the threshold, increment the left pointer to reduce the odd_count.
  3. Add to the result the number of valid subarrays ending at the current right pointer.

This systematic approach ensures optimal counting of the subarrays within the given constraints, using a combination of mathematical computation and efficient looping structures.