# 1248. Count Number of Nice Subarrays

Question link is here.

# Question

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

Example 1:

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

Example 2:

Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.

Example 3:

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16

# Solution

# Solution1: DP

dp[i] = number of odd number in the array up to nums[i]. Therefore, dp[i] - dp[j] == number of odd number in nums[j:i+1]

class Solution:
    def numberOfSubarrays1(self, nums: List[int], k: int) -> int:
        dp = [0 for i in range(len(nums) + 1)]
        cntOdd = 0
        res = 0
        for i, num in enumerate(nums):
            if num % 2 == 1:
                cntOdd += 1
            dp[i+1] = cntOdd
            for j in range(i+1):
                # print(j, i, nums[j:i], cntOdd - dp[j])
                if (cntOdd - dp[j])  == k:
                    res += 1
        # print(dp)
        return res

Time Complxity: $O(n^2)$ , this would leed to TLE.

# Solution2: Sliding window + Pure Math

The problem asks us to find continuous subarray that has k odd numbers in it. We can convert it into how many windows are contains k odd numbers.

For a window [left, right], that starts at an odd number and end at an odd number and contains k odd numbers in it. We can expand the left side of the window to the left until it meets another odd number, let's call this index as firstNotOdd, and we can expand the right side of the window to right until it mees another odd number, let's call this index as LastNotOdd.

The possible combination would be (left - firstNotOdd) * (lastNotOdd - right).

Therefore, we just need to find all possible smallest possible windows.

Two solution are povided below, and the second one is optimized.

class Solution:
    def numberOfSubarrays2(self, nums: List[int], k: int) -> int:
        firstOdd = 0
        LastNoneOdd = 0
        left = 0
        right = 0
        cntOdd = 0
        res = 0
        oddIndex = []
        while right < len(nums) and cntOdd <= k:
            isOdd = nums[right] % 2 == 1
            if isOdd and cntOdd == 0:
                firstOdd = right
            if isOdd:
                oddIndex.append(right)
                cntOdd += 1
            if isOdd and cntOdd == k:
                temp = right + 1
                while temp < len(nums) and nums[temp] % 2 == 0:
                    temp += 1
                lastNoneOdd = temp
                # print(firstOdd, left, right, lastNoneOdd)
                res += (firstOdd - left + 1) * (lastNoneOdd - right)
                left = firstOdd + 1
                right = temp - 1
                oddIndex.pop(0)
                firstOdd = oddIndex[0] if len(oddIndex) >= 1 else None
                cntOdd -= 1
            right += 1
        return res
      
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        res = 0
        oddIndex = [-1]
        for i, num in enumerate(nums):
            if num % 2 == 1:
                oddIndex.append(i)
        oddIndex.append(len(nums))
        left = 1
        right = k
        while right < len(oddIndex) - 1:
            res += (oddIndex[left] - oddIndex[left-1]) * (oddIndex[right+1] - oddIndex[right])
            right += 1
            left += 1
        return res

Time Complexity: $O(n)$

Leetcode 1248

Count Number of Nice Subarrays

# 1248. Count Number of Nice Subarrays

# Question

# Solution

# Solution1: DP

# Solution2: Sliding window + Pure Math