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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Number of Nice Subarrays

Number: 1370

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Amazon, Bloomberg, Deliveroo, Booking.com, Adobe, Walmart Labs, Roblox

Problem Description

Given an array of integers nums and an integer k, a continuous subarray is called nice if there are exactly k odd numbers in it. The task is to determine the number of such nice subarrays.

Key Insights

  • Convert the problem to counting subarrays with a specific "prefix sum" value where the sum represents the count of odd numbers.
  • Use a hash table (or dictionary) to store the frequency of prefix sums encountered.
  • The number of nice subarrays ending at the current index equals the frequency of (current prefix sum - k) seen so far.
  • This approach allows you to find the answer in one pass over the array.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in nums, because we traverse the array once. Space Complexity: O(n), in the worst case where each prefix sum is unique and stored in the hash table.

Solution

We solve the problem using a prefix sum approach. First, we iterate through the array and convert it into a prefix sum representing the cumulative count of odd numbers encountered. As we compute the prefix sums, we use a hash table to record how many times each prefix sum appears. For every current prefix sum value, we check how many times we have seen a prefix sum equal to (current prefix sum - k). The idea is that if prefix[j] - prefix[i] equals k, then between indices i+1 and j, there are exactly k odd numbers. This gives us the count of valid subarrays ending at the current index.

This method works efficiently as it requires only a single pass through the array and maintains a running frequency count using the hash table.

Code Solutions

# Python solution with line-by-line comments

def numberOfSubarrays(nums, k):
    # Initialize dictionary to store frequency of prefix sums
    prefix_count = {0: 1}  # There is one way to have zero odd numbers initially.
    count = 0  # This will store the final count of nice subarrays
    odd_sum = 0  # Prefix sum representing the count of odd numbers so far

    # Iterate through each number in the array
    for num in nums:
        # If the number is odd, increment the odd_count prefix sum
        if num % 2 == 1:
            odd_sum += 1
        
        # If there is a prefix such that (current odd_sum - prefix) equals k,
        # then we found subarrays ending here with k odd numbers
        count += prefix_count.get(odd_sum - k, 0)
        
        # Update the frequency for the current odd_sum in the hash table
        prefix_count[odd_sum] = prefix_count.get(odd_sum, 0) + 1

    # Return the total number of nice subarrays
    return count

# Example usage:
# nums = [1,1,2,1,1]
# k = 3
# print(numberOfSubarrays(nums, k))  # Expected output is 2
← Back to All Questions