1248. Count Number of Nice Subarrays


Problem Description

The problem provides us with an array nums of integers and an integer k. We need to count how many continuous subarrays (a sequence of adjacent elements in the array) have exactly k odd numbers. These subarrays are referred to as nice subarrays.

The main challenge is to do this efficiently for possibly large arrays.

Intuition

To solve this problem, we can apply the concept of prefix sums; however, instead of keeping a running total of the elements, we'll keep a running count of how many odd numbers we've encountered so far. The key idea is to use a map (Counter in Python) to keep track of how many times each count of odd numbers has occurred in our running total (prefix).

Let's say we're iterating through the array and at some point we have encountered x odd numbers. Now, if at an earlier point in the array we had encountered x - k odd numbers, any subarray starting from that earlier point to our current position will have exactly k odd numbers. Why? Because x - (x - k) = k.

So, we use a counter to keep track of all previously seen counts of odd numbers. Every time we hit a new odd number, we increment our current count (t in the code). We then check in our counter to see how many times we've previously seen a count of t - k. The value we get tells us the number of subarrays ending at the current position with exactly k odd numbers.

We add this count to our answer (ans in the code) and move to the next element. Since the subarrays are continuous, we increment our counter for the current count of odd numbers to reflect that we found a new subarray starting point that ends at the current index.

The Counter is initialized with {0: 1} to handle the case where the first k elements form a nice subarray. The count is zero (no odd numbers yet), but we consider it as a valid starting point.

The solution iteratively applies the above logic, using bitwise operations to check if a number is odd (v & 1) and updating the count and answer accordingly.

Learn more about Math and Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The solution uses a Counter dictionary to store the frequency of counts of odd numbers encountered as a prefix sum. This Counter represents how many times each count has been seen so far in the array, which is essential for determining the number of nice subarrays.

Here's a step-by-step breakdown of the implementation:

  1. Initialize a Counter with {0: 1}. This accounts for the prefix sum before we start traversing the array. The value 1 indicates that there's one way to have zero odd numbers so far (essentially, the subarray of length zero).

  2. Initialize two variables, ans and t to 0. ans will hold the final count of nice subarrays, while t will keep the running count of odd numbers seen.

  3. Loop through each number v in the array nums.

    a. Use the bitwise AND operation (v & 1) to determine if v is odd. If so, add 1 to t. The operation v & 1 evaluates to 1 if v is odd, and 0 if v is even.

    b. Calculate t - k, which represents the prefix sum we'd have if we subtracted k odd numbers from the current count. If this value has been seen before (which means there's a subarray ending at an earlier position with t - k odd numbers), we can form a nice subarray ending at the current index. Add the count of t - k from the Counter to ans.

    c. Increment the count of t in the Counter by 1 to indicate that we have encountered another subarray ending at the current index with a prefix sum of t odd numbers.

  4. After the loop completes, ans holds the total count of nice subarrays, and this is what is returned.

Here is how the algorithm works in a nutshell: By maintaining a running count of odd numbers, and having a Counter to record how many times each count has occurred, we can efficiently compute how many subarrays end at a particular index with exactly k odd numbers. This lets us add up the counts for all subarrays in the array just by iterating through it once.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example Walkthrough

Let's consider an example where nums = [1, 2, 3, 4, 5] and k = 2. We want to find out how many continuous subarrays have exactly 2 odd numbers.

Following the solution approach:

  1. We initialize a Counter with {0: 1} to count the number of times we have encountered 0 odd numbers so far (which is once for the empty subarray).

  2. We set ans and t to 0. ans will count our nice subarrays, and t will hold our running tally of odd numbers seen.

  3. We start iterating through each number v in nums.

    • For v = 1: It's odd (since 1 & 1 is 1), so we increment t to 1. We then look for t - k, which is -1. Since -1 is not in our counter, there are 0 subarrays ending here with 2 odd numbers. We update the counter to {0: 1, 1: 1}.

    • For v = 2: It's even (since 2 & 1 is 0), so t remains 1. Looking for t - k (1-2=-1) yields 0 subarrays. Our counter doesn't change.

    • For v = 3: It's odd, t becomes 2. Now, t - k is 0, and since our counter shows {0: 1}, there is 1 subarray ending here with exactly 2 odd numbers. We increment ans to 1 and update the counter to {0: 1, 1: 1, 2: 1}.

    • For v = 4: It's even, so t stays 2. We look for t - k (2-2=0) in the counter, find 1 occurrence, so there's 1 more subarray that meets the criteria. Increment ans to 2, and the counter remains the same.

    • For v = 5: Again, it's odd, t increases to 3. Looking for t - k (3-2=1), we find 1 in the counter. This gives us 1 subarray. ans goes up to 3, and we update the counter to {0: 1, 1: 1, 2: 1, 3: 1}.

  4. After iterating through the array, we have ans as 3, meaning there are three subarrays within nums that contain exactly 2 odd numbers. These subarrays are [1, 2, 3], [3, 4], and [5].

So the function would return 3 as the result. The efficiency of the solution stems from the fact that we only needed to traverse the array once and keep a running tally of our counts in the Counter, which gives us the ability to find the number of nice subarrays in constant time for each element of the array.

Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Python Solution

1from collections import Counter
2
3class Solution:
4    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
5        # Initialize counter for odd counts with 0 count as 1 (base case)
6        odd_count = Counter({0: 1})
7      
8        # Initialize variables for the answer and the temporary count of odds
9        answer = temp_odd_count = 0
10      
11        # Iterate over each value in the list
12        for value in nums:
13            # Increment temp_odd_count if value is odd
14            temp_odd_count += value & 1  # value & 1 is 1 if value is odd, 0 otherwise
15          
16            # If there are at least k odd numbers, add the count to answer
17            # This checks if a valid subarray ending at the current index exists
18            answer += odd_count[temp_odd_count - k]
19          
20            # Increment the count of the current number of odd integers seen so far
21            odd_count[temp_odd_count] += 1
22      
23        # Return the total number of valid subarrays
24        return answer
25

Java Solution

1class Solution {
2    public int numberOfSubarrays(int[] nums, int k) {
3        int n = nums.length; // Length of the input array
4        int[] prefixOddCount = new int[n + 1]; // Array to keep track of the prefix sums of odd numbers
5        prefixOddCount[0] = 1; // There's one way to have zero odd numbers - by taking no elements
6        int result = 0; // Initialize the result count to 0
7        int currentOddCount = 0; // Tracks the current number of odd elements encountered
8
9        // Iterate over each number in the input array
10        for (int num : nums) {
11            // If 'num' is odd, increment the count of odd numbers encountered so far
12            currentOddCount += num & 1;
13          
14            // If we have found at least 'k' odd numbers so far
15            if (currentOddCount - k >= 0) {
16                // Add to 'result' the number of subarrays that have 'k' odd numbers up to this point
17                result += prefixOddCount[currentOddCount - k];
18            }
19          
20            // Increment the count in our prefix sum array for the current odd count
21            prefixOddCount[currentOddCount]++;
22        }
23        return result; // Return the total count of subarrays with exactly 'k' odd numbers
24    }
25}
26

C++ Solution

1#include <vector>
2
3class Solution {
4public:
5    int numberOfSubarrays(std::vector<int>& nums, int k) {
6        int size = nums.size(); // Store the size of the input vector nums
7        std::vector<int> count(size + 1, 0); // Vector to store the count of odd numbers
8        count[0] = 1; // There's one way to have zero odd numbers - empty subarray
9
10        int answer = 0; // Initialize the count of valid subarrays
11        int oddCount = 0; // Counter for the number of odd numbers in the current sequence
12
13        // Iterate through the input numbers
14        for (int num : nums) {
15            oddCount += num & 1; // Increment the odd count if num is odd
16            // If there have been at least k odd numbers so far, update the answer
17            if (oddCount >= k) {
18                answer += count[oddCount - k];
19            }
20            count[oddCount]++; // Increment the count for this number of odd numbers
21        }
22      
23        return answer; // Return the total number of valid subarrays
24    }
25};
26

Typescript Solution

1function numberOfSubarrays(nums: number[], k: number): number {
2    // The length of the input array.
3    const arrayLength = nums.length;
4  
5    // An array to store the count of subarrays with odd numbers sum.
6    const countOfSubarrays = new Array(arrayLength + 1).fill(0);
7  
8    // Base condition: There is always 1 subarray with 0 odd numbers (the empty subarray).
9    countOfSubarrays[0] = 1;
10  
11    // The answer to return that accumulates the number of valid subarrays.
12    let numberOfValidSubarrays = 0;
13  
14    // Tracks the total number of odd numbers encountered so far.
15    let totalOdds = 0;
16  
17    // Iterate through all elements in the array.
18    for (const value of nums) {
19        // If value is odd, increment the count of totalOdds.
20        totalOdds += value & 1;
21      
22        // If there are enough previous odds to form a valid subarray, increment the count.
23        if (totalOdds - k >= 0) {
24            numberOfValidSubarrays += countOfSubarrays[totalOdds - k];
25        }
26      
27        // Increment the count of subarrays we've seen with the current totalOdds.
28        countOfSubarrays[totalOdds] += 1;
29    }
30  
31    // Return the total number of valid subarrays found.
32    return numberOfValidSubarrays;
33}
34
Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Time and Space Complexity

The time complexity of the code is O(n), where n is the number of elements in the nums list. This is because the code iterates through each element of the array exactly once.

During this iteration, the code performs constant-time operations: using bitwise AND to determine the parity of the number, updating the count hashtable, and incrementing the result. The lookup and update of the counter cnt are also expected to be constant time because it is a hashtable.

The space complexity of the code is O(n). In the worst case, if all elements in nums are odd, then the counter cnt can potentially have as many entries as there are elements in nums. Therefore, the size of the counter scales linearly with the size of the input.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫