Jobs

Interviews

Discussions

Count Number of Nice Subarrays

Medium

Count Number of Nice Subarrays

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values in the `nums` array and the value of `k`?
Can the input array `nums` be empty, or can `k` be zero or negative?
If no "nice" subarray exists (i.e., no subarray has exactly `k` odd numbers), what value should I return?
Are the elements in `nums` integers?
Does the order of elements in the subarray matter? In other words, are we looking for contiguous subarrays only?

Brute Force Solution

Approach

The brute force method to find nice subarrays involves checking every single possible subarray within the given list of numbers. For each subarray, we'll count the number of odd numbers it contains and see if that count matches our target. We'll repeat this process for every possible subarray and count how many meet the criteria.

Here's how the algorithm would work step-by-step:

Start with the first number in the list and consider it as a subarray by itself.
Count the number of odd numbers in this subarray.
If the count matches the target number, increase a counter.
Now, consider the first two numbers in the list as a subarray.
Count the odd numbers, check if it matches the target, and update the counter if it does.
Continue extending the subarray from the beginning, one number at a time, until you've considered the entire list.
Then, move to the second number in the list and start again, forming subarrays of increasing length from that point.
Repeat this process, shifting the starting point one number at a time, until you've considered every number as the starting point for a subarray.
The final count will be the total number of 'nice' subarrays.

Code Implementation

def count_number_of_nice_subarrays_brute_force(numbers, target):
    number_of_nice_subarrays = 0

    for start_index in range(len(numbers)): 
        for end_index in range(start_index, len(numbers)): 
            current_subarray = numbers[start_index:end_index+1]
            odd_count = 0

            # Iterate through the subarray and count odd numbers
            for number in current_subarray:
                if number % 2 != 0:
                    odd_count += 1

            # Check if current subarray is "nice"
            if odd_count == target:
                number_of_nice_subarrays += 1

    return number_of_nice_subarrays

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through all possible subarrays of the input array of size n. The outer loop determines the starting index of the subarray, which runs n times. The inner loop extends the subarray from the starting index to the end of the array, leading to a maximum of n iterations. Consequently, the number of operations scales with n * n. This results in approximately n * n/2 operations, simplifying to a time complexity of O(n²).

Space Complexity

O(1) – The brute force approach, as described, primarily involves iterating through subarrays and counting odd numbers within each. No auxiliary data structures like arrays, hashmaps, or stacks are created to store intermediate results or track visited elements beyond the input array itself. The only variables used are loop counters and a variable to store the count of odd numbers within a subarray and a counter for the number of nice subarrays which take constant space. Therefore, the auxiliary space complexity is constant, regardless of the input size N (the number of elements in the array).

Optimal Solution

Approach

Instead of checking every possible group of numbers, the optimal approach cleverly focuses on counting the number of valid groups as it moves through the numbers one by one. It tracks how many groups ending at each position meet the requirement of having a specific number of odd numbers.

Here's how the algorithm would work step-by-step:

Start at the beginning of the list of numbers and keep track of how many odd numbers you've seen so far.
As you move to the next number, check if it's odd or even and update your count of odd numbers.
At each step, figure out how many groups ending at this number have exactly the right number of odd numbers that you're looking for.
To do this efficiently, keep track of how many groups ended at previous positions with different counts of odd numbers.
Specifically, when you're at a number and want to know how many groups ending there have the target number of odd numbers, you just need to look back and see how many groups ended at previous positions with the difference between the target and your current odd number count.
Add the number of such previous groups to your total count of valid groups.
Repeat these steps until you've gone through all the numbers in the list.

Code Implementation

def count_number_of_nice_subarrays(numbers, target):
    odd_count_so_far = 0
    nice_subarrays_count = 0
    # Store frequency of odd number counts seen.
    odd_counts = {0: 1}

    for number in numbers:
        if number % 2 != 0:
            odd_count_so_far += 1

        # Determine needed prior odd count.
        needed_odd_count = odd_count_so_far - target

        # Add subarrays ending here if a prior count exists
        if needed_odd_count in odd_counts:
            nice_subarrays_count += odd_counts[needed_odd_count]

        # Update the frequency of the current odd number count
        if odd_count_so_far in odd_counts:
            odd_counts[odd_count_so_far] += 1
        else:
            odd_counts[odd_count_so_far] = 1

    return nice_subarrays_count

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the input array of size n once. Inside the loop, it performs constant time operations to update the odd number count and retrieve the count of previous subarrays with a specific odd number count using a hash map (or similar data structure that provides O(1) average time complexity for insertion and retrieval). Therefore, the overall time complexity is directly proportional to the number of elements in the array, resulting in O(n).

Space Complexity

O(N) – The solution uses a data structure to keep track of how many groups ended at previous positions with different counts of odd numbers. In the worst-case scenario, the number of odd numbers seen so far could range from 0 to N (where N is the number of elements in the input array), requiring storage for each possible count. Therefore, the auxiliary space used grows linearly with the input size N. This creates a need to store information about each of the N positions within the array in a HashMap or array.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as there are no subarrays in an empty array.
k is zero	Count subarrays with only even numbers, which can be done with sliding window.
k is greater than the number of odd numbers in the array	Return 0, as it's impossible to have k odd numbers in a subarray.
Array contains only even numbers and k > 0	Return 0, because no subarray can have odd numbers.
Large input array size and potentially many nice subarrays - scalability	Prefix sum and hash map approach is preferred for better time complexity.
Integer overflow if counting very large number of subarrays	Use appropriate data types (e.g., long) for counting subarrays.
Array contains negative numbers	The sign of numbers does not affect the odd/even determination, so treat them the same as positive numbers.
Array contains zero values	Zeros are even numbers and do not impact the count of odd numbers.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values in the `nums` array and the value of `k`?
Can the input array `nums` be empty, or can `k` be zero or negative?
If no "nice" subarray exists (i.e., no subarray has exactly `k` odd numbers), what value should I return?
Are the elements in `nums` integers?
Does the order of elements in the subarray matter? In other words, are we looking for contiguous subarrays only?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first number in the list and consider it as a subarray by itself.
Count the number of odd numbers in this subarray.
If the count matches the target number, increase a counter.
Now, consider the first two numbers in the list as a subarray.
Count the odd numbers, check if it matches the target, and update the counter if it does.
Continue extending the subarray from the beginning, one number at a time, until you've considered the entire list.
Then, move to the second number in the list and start again, forming subarrays of increasing length from that point.
Repeat this process, shifting the starting point one number at a time, until you've considered every number as the starting point for a subarray.
The final count will be the total number of 'nice' subarrays.

Code Implementation

def count_number_of_nice_subarrays_brute_force(numbers, target):
    number_of_nice_subarrays = 0

    for start_index in range(len(numbers)): 
        for end_index in range(start_index, len(numbers)): 
            current_subarray = numbers[start_index:end_index+1]
            odd_count = 0

            # Iterate through the subarray and count odd numbers
            for number in current_subarray:
                if number % 2 != 0:
                    odd_count += 1

            # Check if current subarray is "nice"
            if odd_count == target:
                number_of_nice_subarrays += 1

    return number_of_nice_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the list of numbers and keep track of how many odd numbers you've seen so far.
As you move to the next number, check if it's odd or even and update your count of odd numbers.
At each step, figure out how many groups ending at this number have exactly the right number of odd numbers that you're looking for.
To do this efficiently, keep track of how many groups ended at previous positions with different counts of odd numbers.
Specifically, when you're at a number and want to know how many groups ending there have the target number of odd numbers, you just need to look back and see how many groups ended at previous positions with the difference between the target and your current odd number count.
Add the number of such previous groups to your total count of valid groups.
Repeat these steps until you've gone through all the numbers in the list.

Code Implementation

def count_number_of_nice_subarrays(numbers, target):
    odd_count_so_far = 0
    nice_subarrays_count = 0
    # Store frequency of odd number counts seen.
    odd_counts = {0: 1}

    for number in numbers:
        if number % 2 != 0:
            odd_count_so_far += 1

        # Determine needed prior odd count.
        needed_odd_count = odd_count_so_far - target

        # Add subarrays ending here if a prior count exists
        if needed_odd_count in odd_counts:
            nice_subarrays_count += odd_counts[needed_odd_count]

        # Update the frequency of the current odd number count
        if odd_count_so_far in odd_counts:
            odd_counts[odd_count_so_far] += 1
        else:
            odd_counts[odd_count_so_far] = 1

    return nice_subarrays_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as there are no subarrays in an empty array.
k is zero	Count subarrays with only even numbers, which can be done with sliding window.
k is greater than the number of odd numbers in the array	Return 0, as it's impossible to have k odd numbers in a subarray.
Array contains only even numbers and k > 0	Return 0, because no subarray can have odd numbers.
Large input array size and potentially many nice subarrays - scalability	Prefix sum and hash map approach is preferred for better time complexity.
Integer overflow if counting very large number of subarrays	Use appropriate data types (e.g., long) for counting subarrays.
Array contains negative numbers	The sign of numbers does not affect the odd/even determination, so treat them the same as positive numbers.
Array contains zero values	Zeros are even numbers and do not impact the count of odd numbers.