Problem

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.

Examples

Example 1:

1
2
3

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:

1
2
3

Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There are no odd numbers in the array.

Example 3:

1
2

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

Solution

Method 1 - Using Prefix counts and sliding window

We can follow this approach:

  1. Build an 1-indexed prefix sum array prefixOddCnt for counting odd numbers in subarrays nums[0:i]
  2. Use sliding window pattern to solve like the following. It’s to see that prefixOddCnt(nums[l..r]) can be easily computed by using prefix sums

We need 1 indexed prefix array, as we need to count from 0 to n, i.e. we also need to handle the initial state before even processing any element.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Solution {

	public int numberOfSubarrays(int[] nums, int k) {
		int n = nums.length;
		int[] prefixOddCnt = new int[n + 1];

		for (int i = 0; i < n; i++) {
			prefixOddCnt[i + 1] += prefixOddCnt[i] + (nums[i] & 1);
		}

		int l = 0, ans = 0;

		for (int r = 0; r < n; r++) {
			// Ensure the current window [l, r] has at least k odd numbers
			while (l <= r && prefixOddCnt[r + 1] - prefixOddCnt[l] > k) {
				l++;
			}

			// If the current window [l, r] has exactly k odd numbers
			if (prefixOddCnt[r + 1] - prefixOddCnt[l] == k) {
				int i = l; // check how much we can slide l
				// Count nice subarrays ending at r
				while (i <= r && prefixOddCnt[r + 1] - prefixOddCnt[i] == k) {
					ans++;
					i++;
				}
			}
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n) - where n is the number of elements in nums. O(n) for forming prefix count array and O(n) in sliding window, where each number is processed once. So, total time complexity = O(n) + O(n) = O(n)
  • 🧺 Space complexity: O(n), for the prefixOddCnt array.

Dry Run

Initialization
1

nums = [1, 1, 2, 1, 1], k = 3, n = 5, count = 0
Create Prefix Count
1
2

nums          =    [1, 1, 2, 1, 1]
prefixOddCnt  = [0, 1, 2, 2, 3, 4]
Sliding Window Algorithm
First Iteration (r = 0)
1
2

prefixOddCnt[1] - prefixOddCnt[0] = 1 - 0 = 1
1 < 3 => We will extned the window
Second Iteration (r = 1)
1
2

prefixOddCnt[3] - prefixOddCnt[0] = 2 - 0 = 2
2 < 3 => We will extned the window
Third Iteration (r = 2)
1
2

prefixOddCnt[3] - prefixOddCnt[0] = 2 - 0 = 2
2 < 3 => We will extned the window
Fourth Iteration (r = 3)
1

prefixOddCnt[4] - prefixOddCnt[0] = 3 - 0 = 3

Now, we have a window with exactly k odd numbers. Slide l to count the nice subarrays ending at r.

Inner Loop (i iterates from l):

1
2

 i = 0: prefixOddCnt[4] - prefixOddCnt[0] = 3 - 0 = 3, ans = 1, i = 1
 i = 1: prefixOddCnt[4] - prefixOddCnt[1] = 3 - 1 = 2 (break the loop as 2 != 3)
Fifth Iteration (r = 4)
1
2

prefixOddCnt[5] - prefixOddCnt[0] = 4 - 0 = 4
This is greater than 3. Move l to reduce the window size.

After moving window size:

1

l = 1, prefixOddCnt[5] - prefixOddCnt[1] = 4 - 1 = 3 (now we have a valid window)

Inner Loop - count the good subarrays (i iterates from l):

1
2

 i = 1: prefixOddCnt[5] - prefixOddCnt[1] = 4 - 1 = 3, ans = 2, i = 2
 i = 2: prefixOddCnt[5] - prefixOddCnt[2] = 4 - 2 = 2 (break the loop as 2 != 3)
Result

After traversing the whole array, the total number of nice subarrays is 2.