Jobs

Interviews

Discussions

Count Number of Nice Subarrays

Medium

Roblox

0 views

Topics:

ArraysTwo PointersSliding Windows

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 are no odd numbers in the array.

Example 3:

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

Constraints:

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

Count Number of Nice Subarrays

Medium

Roblox

0 views

Topics:

ArraysTwo PointersSliding Windows

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 are no odd numbers in the array.

Example 3:

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

Constraints:

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

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 constraints on the size of the input array `nums` and the value of `k`?
Can the integers in the `nums` array be negative, zero, or only positive?
If there are no nice subarrays, should I return 0?
Are overlapping subarrays considered distinct? For example, if `nums` is [1,1,1,1,1] and `k` is 2, should I count [1,1] and [1,1] appearing later as different?
Is `k` guaranteed to be non-negative and not larger than the size of the array?

Brute Force Solution

Approach

To solve this problem the hard way, we're going to examine every single possible group of numbers within the given set. For each group, we'll check if it meets our specific criteria for being 'nice'.

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

First, look at every single number in the set by itself. Check if that one number meets the 'nice' criteria.
Next, look at every possible pair of numbers next to each other. Check if each pair meets the 'nice' criteria.
Then, look at every possible group of three numbers next to each other. Check if each group of three meets the 'nice' criteria.
Keep doing this, making the groups larger each time, until you consider the entire set of numbers as one big group.
Every time you find a group that meets the 'nice' criteria, count it.
At the very end, add up all the groups you counted to find the total number of 'nice' groups.

Code Implementation

def count_number_nice_subarrays_brute_force(numbers, target_odd_count):
    number_of_nice_subarrays = 0
    array_length = len(numbers)

    for subarray_size in range(1, array_length + 1):

        # Iterate through all possible subarrays of the current size
        for start_index in range(array_length - subarray_size + 1):
            end_index = start_index + subarray_size
            subarray = numbers[start_index:end_index]
            odd_count = 0

            # Count odd numbers in the current subarray
            for number in subarray:
                if number % 2 != 0:
                    odd_count += 1

            # Check if the current subarray is "nice"
            if odd_count == target_odd_count:

                # Increment the count if the subarray is nice
                number_of_nice_subarrays += 1

    return number_of_nice_subarrays

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible subarrays. The outer loop considers all starting positions (n iterations). The inner loop considers all ending positions for each starting position (n iterations). Inside the inner loops, the algorithm checks if the current subarray is 'nice', which involves counting odd numbers and takes O(n) time in the worst case. Therefore, the total time complexity is O(n * n * n) which simplifies to O(n³).

Space Complexity

O(1) – The provided plain English explanation describes an iterative approach examining all possible subarrays. It doesn't mention any explicit auxiliary data structures like arrays, lists, or hash maps being created. It appears that the counts of 'nice' subarrays are updated in place (not requiring extra memory). Therefore, the space complexity remains constant, independent of the input size N.

Optimal Solution

Approach

Instead of checking every possible group of numbers, we use a sliding window approach. We expand and shrink the window based on whether the number of odd numbers within that window meets our target.

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

Keep track of the number of odd numbers within a sliding window.
Expand the window (add numbers to the right) until the count of odd numbers equals the desired amount.
Once the number of odd numbers is correct, count how many valid subarrays start at the left side of the current window. This is the number of even numbers to the left of the first odd number, plus one.
Then, shrink the window from the left until the count of odd numbers decreases by one. Keep counting valid subarrays by determining the number of even numbers to the left of the new first odd number.
Move the window to the right and repeat the process of expanding and shrinking, counting the valid subarrays at each step.
The total count of all the valid subarrays found is the final answer.

Code Implementation

def count_number_of_nice_subarrays(numbers, target):
    number_of_odd_numbers = 0
    left_window_boundary = 0
    nice_subarray_count = 0

    for right_window_boundary in range(len(numbers)):
        if numbers[right_window_boundary] % 2 != 0:
            number_of_odd_numbers += 1

        # Shrink window when odd count exceeds target.
        while number_of_odd_numbers > target:
            if numbers[left_window_boundary] % 2 != 0:
                number_of_odd_numbers -= 1
            left_window_boundary += 1

        # Count subarrays if odd count equals target.
        if number_of_odd_numbers == target:
            even_numbers_to_left = 0
            temporary_left_boundary = left_window_boundary

            # Count leading even numbers to find valid subarrays.
            while numbers[temporary_left_boundary] % 2 == 0:
                even_numbers_to_left += 1
                temporary_left_boundary += 1

            nice_subarray_count += even_numbers_to_left + 1

    return nice_subarray_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array using a sliding window. The left and right pointers of the window only move forward, so each element is visited at most twice: once by the right pointer when expanding the window and once by the left pointer when shrinking it. Therefore, the number of operations is proportional to the size of the input array (n), leading to a time complexity of O(n).

Space Complexity

O(1) – The provided solution uses a sliding window approach to count "nice" subarrays. It maintains a count of odd numbers within the window and adjusts the window's boundaries based on this count. No auxiliary data structures like lists, hash maps, or recursion are used. The algorithm only uses a few integer variables to store indices and the count of odd numbers, which takes up constant extra space regardless of the input array size N. Thus, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0 immediately, as there are no subarrays to evaluate.
k is zero and array contains no odd numbers	The entire array constitutes a nice subarray, so we need to count total number of sub-arrays.
k is larger than the number of odd numbers in the array	Return 0, as it's impossible to form a nice subarray with more odd numbers than available.
Array contains only even numbers and k > 0	Return 0 because there are no odd numbers to form a nice subarray with k odd numbers.
Array contains negative numbers	The solution should work correctly as the 'oddness' of a number is determined by checking if its remainder when divided by 2 is 1 or -1, which we should account for.
Large input array (nums.length is very large)	A sliding window or prefix sum approach ensures a time complexity of O(n), preventing time limit exceeded errors.
k is negative	Return 0 immediately, as a negative number of odd numbers is not a valid target.
Integer overflow possible when calculating the number of subarrays	Use 'long' data type to store number of subarrays, if needed in a particular language.

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 constraints on the size of the input array `nums` and the value of `k`?
Can the integers in the `nums` array be negative, zero, or only positive?
If there are no nice subarrays, should I return 0?
Are overlapping subarrays considered distinct? For example, if `nums` is [1,1,1,1,1] and `k` is 2, should I count [1,1] and [1,1] appearing later as different?
Is `k` guaranteed to be non-negative and not larger than the size of the array?

Brute Force Solution

Approach

To solve this problem the hard way, we're going to examine every single possible group of numbers within the given set. For each group, we'll check if it meets our specific criteria for being 'nice'.

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

First, look at every single number in the set by itself. Check if that one number meets the 'nice' criteria.
Next, look at every possible pair of numbers next to each other. Check if each pair meets the 'nice' criteria.
Then, look at every possible group of three numbers next to each other. Check if each group of three meets the 'nice' criteria.
Keep doing this, making the groups larger each time, until you consider the entire set of numbers as one big group.
Every time you find a group that meets the 'nice' criteria, count it.
At the very end, add up all the groups you counted to find the total number of 'nice' groups.

Code Implementation

def count_number_nice_subarrays_brute_force(numbers, target_odd_count):
    number_of_nice_subarrays = 0
    array_length = len(numbers)

    for subarray_size in range(1, array_length + 1):

        # Iterate through all possible subarrays of the current size
        for start_index in range(array_length - subarray_size + 1):
            end_index = start_index + subarray_size
            subarray = numbers[start_index:end_index]
            odd_count = 0

            # Count odd numbers in the current subarray
            for number in subarray:
                if number % 2 != 0:
                    odd_count += 1

            # Check if the current subarray is "nice"
            if odd_count == target_odd_count:

                # Increment the count if the subarray is nice
                number_of_nice_subarrays += 1

    return number_of_nice_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Instead of checking every possible group of numbers, we use a sliding window approach. We expand and shrink the window based on whether the number of odd numbers within that window meets our target.

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

Keep track of the number of odd numbers within a sliding window.
Expand the window (add numbers to the right) until the count of odd numbers equals the desired amount.
Once the number of odd numbers is correct, count how many valid subarrays start at the left side of the current window. This is the number of even numbers to the left of the first odd number, plus one.
Then, shrink the window from the left until the count of odd numbers decreases by one. Keep counting valid subarrays by determining the number of even numbers to the left of the new first odd number.
Move the window to the right and repeat the process of expanding and shrinking, counting the valid subarrays at each step.
The total count of all the valid subarrays found is the final answer.

Code Implementation

def count_number_of_nice_subarrays(numbers, target):
    number_of_odd_numbers = 0
    left_window_boundary = 0
    nice_subarray_count = 0

    for right_window_boundary in range(len(numbers)):
        if numbers[right_window_boundary] % 2 != 0:
            number_of_odd_numbers += 1

        # Shrink window when odd count exceeds target.
        while number_of_odd_numbers > target:
            if numbers[left_window_boundary] % 2 != 0:
                number_of_odd_numbers -= 1
            left_window_boundary += 1

        # Count subarrays if odd count equals target.
        if number_of_odd_numbers == target:
            even_numbers_to_left = 0
            temporary_left_boundary = left_window_boundary

            # Count leading even numbers to find valid subarrays.
            while numbers[temporary_left_boundary] % 2 == 0:
                even_numbers_to_left += 1
                temporary_left_boundary += 1

            nice_subarray_count += even_numbers_to_left + 1

    return nice_subarray_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0 immediately, as there are no subarrays to evaluate.
k is zero and array contains no odd numbers	The entire array constitutes a nice subarray, so we need to count total number of sub-arrays.
k is larger than the number of odd numbers in the array	Return 0, as it's impossible to form a nice subarray with more odd numbers than available.
Array contains only even numbers and k > 0	Return 0 because there are no odd numbers to form a nice subarray with k odd numbers.
Array contains negative numbers	The solution should work correctly as the 'oddness' of a number is determined by checking if its remainder when divided by 2 is 1 or -1, which we should account for.
Large input array (nums.length is very large)	A sliding window or prefix sum approach ensures a time complexity of O(n), preventing time limit exceeded errors.
k is negative	Return 0 immediately, as a negative number of odd numbers is not a valid target.
Integer overflow possible when calculating the number of subarrays	Use 'long' data type to store number of subarrays, if needed in a particular language.