☕ DSA Java Articles

Topics › Sliding Window and Two Pointers › Medium Problems

Count number of Nice subarrays

Hard TUF ID 924 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an integer array nums and an integer k. A subarray (a contiguous block) is nice if it contains exactly k odd numbers. Return the number of nice subarrays.

Only the parity of each element matters. If you replace every element by 1 when it is odd and 0 when it is even, a nice subarray is exactly a subarray whose sum is k. So this is the binary “count subarrays with sum k” problem in disguise.

Constraints: 1 ≤ n ≤ 5 × 10^4, 1 ≤ nums[i] ≤ 10^5, 1 ≤ k ≤ n. The answer is at most n(n + 1) / 2 ≈ 1.25 × 10^9, which still fits in an int.

Example 1

nums = [1, 1, 2, 1, 1], k = 3
answer = 2          // [1,1,2,1] and [1,2,1,1]

Example 2

nums = [2, 2, 2, 1, 2, 2, 1, 2, 2, 2], k = 2
answer = 16         // the two 1s must both be inside; 4 ways to choose the left end, 4 for the right end

Approach 1: Brute force

Intuition. For every start i, extend the end j and keep a running count of odd numbers. Count the subarray when the count equals k. The count never decreases as j moves right, so once it exceeds k we can stop extending this start.

The parity test uses x & 1 rather than x % 2. In Java -3 % 2 is -1, so x % 2 == 1 silently misses negative odd numbers, while x & 1 is 1 for every odd int in two’s complement.

Algorithm.

  1. For each i: odd = 0.
  2. For j = i ..: add nums[j] & 1. If odd == k, count; if odd > k, break.
  3. Return the count.
static int bruteForce(int[] nums, int k) {
    int n = nums.length, count = 0;
    for (int i = 0; i < n; i++) {
        int odd = 0;
        for (int j = i; j < n; j++) {
            odd += nums[j] & 1;                    // & 1 is 1 for odd values, negatives included
            if (odd == k) count++;
            else if (odd > k) break;
        }
    }
    return count;
}

Complexity. Time O(n^2): an all-even array with k = 1 never breaks early. Space O(1).

Approach 2: Better, prefix counts

Intuition. Let P[t] be the number of odd values among the first t elements, with P[0] = 0. The subarray nums[i..j] contains P[j + 1] - P[i] odd numbers, so it is nice exactly when P[i] = P[j + 1] - k. Scan once, and for each new prefix count look up how many earlier prefixes had the value prefix - k.

Because a prefix count lies between 0 and n, a plain int[n + 1] array replaces the hash map you would need for general prefix sums.

Algorithm.

  1. freq[0] = 1 (the empty prefix), odd = 0, count = 0.
  2. For each x: odd += x & 1; if odd >= k, add freq[odd - k]; then increment freq[odd].
  3. Return count.
static int better(int[] nums, int k) {
    int[] freq = new int[nums.length + 1];         // prefix odd counts lie in 0..n
    freq[0] = 1;
    int odd = 0, count = 0;
    for (int x : nums) {
        odd += x & 1;
        if (odd >= k) count += freq[odd - k];
        freq[odd]++;
    }
    return count;
}

Complexity. Time O(n). Space O(n) for the frequency array.

Approach 3: Optimal, “at most” minus “at most”

Intuition. A sliding window cannot directly count “exactly k odd numbers”: for a fixed right end, the nice subarrays do not form one window but a whole range of starts, because even numbers can be added on the left without changing the odd count. A window can count “at most k odd numbers” easily, because that property survives shrinking. So we use:

nice subarrays = (subarrays with at most k odds) − (subarrays with at most k − 1 odds).

For atMost(k): extend r; while the window holds more than k odd numbers, move l right. Now every start from l to r gives a subarray ending at r with at most k odd numbers, so add r - l + 1. Each subarray is counted once, at its right end.

Algorithm.

  1. atMost(k): return 0 if k < 0; otherwise run the window as described and return the total.
  2. Return atMost(k) - atMost(k - 1).
static int optimal(int[] nums, int k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}

static int atMost(int[] nums, int k) {
    if (k < 0) return 0;
    int l = 0, odd = 0, count = 0;
    for (int r = 0; r < nums.length; r++) {
        odd += nums[r] & 1;
        while (odd > k) {
            odd -= nums[l] & 1;
            l++;
        }
        count += r - l + 1;                        // subarrays ending at r with at most k odd numbers
    }
    return count;
}

Dry run on nums = [1, 1, 2, 1, 1], k = 3. Parities are [1, 1, 0, 1, 1].

r atMost(3): l adds atMost(2): l adds
0 0 1 0 1
1 0 2 0 2
2 0 3 0 3
3 0 4 1 3
4 1 4 2 3
total   14   12

At r = 3 the atMost(2) window [0..3] holds three odds, so l moves to 1; at r = 4 it again holds three, so l moves to 2. The answer is 14 − 12 = 2, the subarrays [1,1,2,1] and [1,2,1,1].

Complexity. Time O(n): two linear window passes. Space O(1).

A single-window variant also exists: track how many even numbers sit before the first odd number of the window, since each is an extra valid start. It has the same O(n) cost, but the “at most” difference is easier to get right and reuses the code from the binary-sum problem, so it is the one worth remembering.

Edge cases and pitfalls