1248. Count Number of Nice Subarrays

Intuition

To solve the problem of finding the number of "nice" subarrays (subarrays with exactly k odd numbers), we can use a two-pointer (or sliding window) approach. The idea is to maintain a window of elements that contains exactly k odd numbers and calculate how many such subarrays can be formed by shifting the window along the array.

Approach

1. Initialize Variables: Start with two pointers, l (left) and r (right), both set to the beginning of the array. Use a variable res to count the number of nice subarrays, and count to keep track of the number of odd numbers in the current window.
2. Expand the Window: Move the right pointer r to the right, expanding the window until the window contains exactly k odd numbers.
3. Count Subarrays: Once the window contains exactly k odd numbers, count how many subarrays end at r and start at positions between l and the current l. Increment res by the number of valid subarrays.
4. Shrink the Window: Move the left pointer l to the right to reduce the number of odd numbers in the window. Adjust l until the window no longer contains k odd numbers.
5. Repeat: Repeat steps 2-4 until the right pointer r reaches the end of the array.
6. Return Result: Return the total count of nice subarrays stored in res.

The approach ensures that we efficiently count the number of subarrays by leveraging the sliding window technique, which avoids the need for nested loops and thus improves performance.

Complexity

• Time Complexity: O(n), where n is the length of the input array. Each element is processed at most twice (once by the right pointer and once by the left pointer).
• Space Complexity: O(1), since we only use a fixed amount of extra space for pointers and counters.

Code

C++

class Solution {
public:
    int numberOfSubarrays(vector& nums, int k) {
        int n = nums.size();
        int l = 0, r = 0, res = 0;

        while (r < n) {
            while (r < n && k > 0) if (nums[r++] % 2 != 0) --k;
            int i = l;
            int j = r;
            while (l < r && nums[l] % 2 == 0) ++l;
            while (r < n && nums[r] % 2 == 0) ++r;
            if (k == 0) res += (l - i + 1) * (r - j + 1);
            ++l, ++k;
        }

        return res;
    }
};

Python

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        l = 0
        r = 0
        res = 0

        while r < n:
            while r < n and k > 0:
                if nums[r] % 2 != 0:
                    k -= 1
                r += 1

            i = l
            j = r

            while l < r and nums[l] % 2 == 0:
                l += 1

            while r < n and nums[r] % 2 == 0:
                r += 1

            if k == 0:
                res += (l - i + 1) * (r - j + 1)

            l += 1
            k += 1

        return res

Java

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length;
        int l = 0, r = 0, res = 0;

        while (r < n) {
            while (r < n && k > 0) if (nums[r++] % 2 != 0) k--;
            int i = l;
            int j = r;
            while (l < r && nums[l] % 2 == 0) l++;
            while (r < n && nums[r] % 2 == 0) r++;
            if (k == 0) res += (l - i + 1) * (r - j + 1);
            l++;
            k++;
        }

        return res;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numberOfSubarrays = function (nums, k) {
  var n = nums.length;
  var l = 0;
  var r = 0;
  var res = 0;

  while (r < n) {
    while (r < n && k) if (nums[r++] & 1) --k;
    i = l;
    j = r;
    while (l < r && !(nums[l] & 1)) ++l;
    while (r < n && !(nums[r] & 1)) ++r;
    if (!k) res += (l - i + 1) * (r - j + 1);
    ++l, ++k;
  }

  return res;
};

Go

func numberOfSubarrays(nums []int, k int) int {
	n := len(nums)
	l := 0
	r := 0
	res := 0

	for r < n {
		for r < n && k > 0 {
			if nums[r] % 2 != 0 {
				k--
			}
			r++
		}
		i := l
		j := r
		for l < r && nums[l] % 2 == 0 {
			l++
		}
		for r < n && nums[r] % 2 == 0 {
			r++
		}
		if k == 0 {
			res += (l - i + 1) * (r - j + 1)
		}
		l++
		k++
	}

	return res
}

C#

public class Solution {
    public int NumberOfSubarrays(int[] nums, int k) {
        int n = nums.Length;
        int l = 0, r = 0, res = 0;

        while (r < n) {
            while (r < n && k > 0) if (nums[r++] % 2 != 0) k--;
            int i = l;
            int j = r;
            while (l < r && nums[l] % 2 == 0) l++;
            while (r < n && nums[r] % 2 == 0) r++;
            if (k == 0) res += (l - i + 1) * (r - j + 1);
            l++;
            k++;
        }

        return res;
    }
}