We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Number of Nice Subarrays

Difficulty: Medium

Problem Description

Given an array of integers nums and an integer k, a continuous subarray is called nice if there are k odd numbers in it. Return the number of nice sub-arrays.

Key Insights

  • A subarray is defined by its start and end indices, and can be identified by counting the number of odd numbers within it.
  • The problem can be approached using a sliding window technique or a prefix sum approach to efficiently count subarrays with exactly k odd numbers.
  • To count the nice subarrays effectively, we can make use of a helper function that counts the number of subarrays with at most k odd numbers and then use this to derive the result.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a two-pointer technique (sliding window) to track the count of odd numbers in the current window. The main idea is to create a helper function that counts the number of subarrays with at most k odd numbers. The result is then computed by taking the difference between the counts of subarrays with at most k and at most k-1 odd numbers.

Code Solutions

def atMostK(nums, k):
    count = 0
    left = 0
    for right in range(len(nums)):
        if nums[right] % 2 == 1:
            k -= 1
        while k < 0:
            if nums[left] % 2 == 1:
                k += 1
            left += 1
        count += right - left + 1
    return count

def countNiceSubarrays(nums, k):
    return atMostK(nums, k) - atMostK(nums, k - 1)

# Example usage:
nums = [1, 1, 2, 1, 1]
k = 3
print(countNiceSubarrays(nums, k))  # Output: 2
← Back to All Questions