Count Number of Nice Subarrays with Exactly K Odd Numbers

Given an integer array nums and an integer k, return the number of nice subarrays.

A nice subarray is a contiguous subarray that contains exactly k odd numbers.

Example:
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The nice subarrays are [1,1,2,1] and [1,2,1,1].

Understanding the Problem

We are given an integer array nums and an integer k. Our goal is to count how many contiguous subarrays (or continuous slices of the array) have exactly k odd numbers.

These subarrays are called nice subarrays.

For example:

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

Nice subarrays with exactly 3 odd numbers: [1, 1, 2, 1] and [1, 2, 1, 1].

Step-by-Step Solution with Example

Step 1: Reframe the Problem

Instead of directly counting subarrays with exactly k odd numbers, we count:

• Subarrays with at most k odd numbers
• Subarrays with at most k-1 odd numbers

The number of subarrays with exactly k odd numbers is the difference:

exactlyK(k) = atMost(k) - atMost(k - 1)

Step 2: Understand the Helper Function atMost(k)

This function counts how many subarrays have at most k odd numbers using the sliding window approach.

• We use two pointers: left and right.
• We move the right pointer one step at a time and track the number of odd numbers in the current window.
• If the count of odd numbers exceeds k, we move the left pointer to shrink the window.
• At every step, we add right - left + 1 to the result because that’s how many valid subarrays end at right.

Step 3: Walk Through the Example [1, 1, 2, 1, 1] with k = 3

Let’s compute atMost(3) first:

• right = 0, num = 1 → oddCount = 1, subarrays = 1
• right = 1, num = 1 → oddCount = 2, subarrays = 3
• right = 2, num = 2 → even, oddCount = 2, subarrays = 6
• right = 3, num = 1 → oddCount = 3, subarrays = 10
• right = 4, num = 1 → oddCount = 4 → exceed k → move left to reduce oddCount = 3 → subarrays = 14

So, atMost(3) = 14

Now compute atMost(2) using similar steps and you’ll get 12.

Final count = 14 - 12 = 2, which matches our expected output.

Step 4: Implement in Code

def numberOfSubarrays(nums, k):
    def atMost(k):
        left = 0
        count = 0
        oddCount = 0

        for right in range(len(nums)):
            if nums[right] % 2 == 1:
                oddCount += 1
            while oddCount > k:
                if nums[left] % 2 == 1:
                    oddCount -= 1
                left += 1
            count += right - left + 1
        return count

    return atMost(k) - atMost(k - 1)

Edge Cases

• All even numbers: If nums contains no odd numbers, the answer will be 0 unless k == 0.
• All odd numbers: Can form many nice subarrays. Be careful with boundaries and window resizing.
• Empty array: Should return 0 safely.
• k greater than total odd numbers: No subarray can satisfy, so answer is 0.

Final Thoughts

This problem becomes manageable by converting the exact count question into a more flexible "at most" count using the sliding window technique. It’s an elegant way to reduce complexity and helps you gain insight into how prefix counts and window shrinking work together.

By following the logic carefully and considering all edge cases, beginners can confidently solve such array problems using two-pointer strategies.

1. Define a helper function atMost(k) that returns the count of subarrays with at most k odd numbers.
2. Use a sliding window with two pointers left and right.
3. Keep a counter oddCount to track the number of odd numbers in the current window.
4. Initialize a result counter res = 0.
5. Traverse the array with the right pointer:
6. → If nums[right] is odd, decrement k (or increment oddCount).
7. → While oddCount > k, move the left pointer forward and adjust oddCount if needed.
8. → For each right, add (right - left + 1) to the result, which represents subarrays ending at right.
9. Finally, return atMost(k) - atMost(k-1) to get the count of subarrays with exactly k odd numbers.

#include <stdio.h>

int atMost(int* nums, int numsSize, int k) {
    int left = 0, right = 0, count = 0, oddCount = 0;
    for (right = 0; right < numsSize; right++) {
        if (nums[right] % 2 != 0) oddCount++;
        while (oddCount > k) {
            if (nums[left] % 2 != 0) oddCount--;
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

int numberOfNiceSubarrays(int* nums, int numsSize, int k) {
    return atMost(nums, numsSize, k) - atMost(nums, numsSize, k - 1);
}

int main() {
    int nums[] = {1,1,2,1,1};
    int k = 3;
    int size = sizeof(nums) / sizeof(nums[0]);
    int result = numberOfNiceSubarrays(nums, size, k);
    printf("Number of nice subarrays: %d\n", result); // Output: 2
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int atMost(const vector<int>& nums, int k) {
    int left = 0, count = 0, oddCount = 0;
    for (int right = 0; right < nums.size(); right++) {
        if (nums[right] % 2 != 0) oddCount++;
        while (oddCount > k) {
            if (nums[left] % 2 != 0) oddCount--;
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

int numberOfNiceSubarrays(const vector<int>& nums, int k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}

int main() {
    vector<int> nums = {1,1,2,1,1};
    int k = 3;
    int result = numberOfNiceSubarrays(nums, k);
    cout << "Number of nice subarrays: " << result << endl; // 2
    return 0;
}

def atMost(nums, k):
    left = 0
    count = 0
    oddCount = 0
    for right in range(len(nums)):
        if nums[right] % 2 != 0:
            oddCount += 1
        while oddCount > k:
            if nums[left] % 2 != 0:
                oddCount -= 1
            left += 1
        count += right - left + 1
    return count

def numberOfNiceSubarrays(nums, k):
    return atMost(nums, k) - atMost(nums, k - 1)

# Example usage
nums = [1,1,2,1,1]
k = 3
result = numberOfNiceSubarrays(nums, k)
print(f"Number of nice subarrays: {result}")  # Output: 2

public class NiceSubarrays {
    private static int atMost(int[] nums, int k) {
        int left = 0, count = 0, oddCount = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] % 2 != 0) oddCount++;
            while (oddCount > k) {
                if (nums[left] % 2 != 0) oddCount--;
                left++;
            }
            count += right - left + 1;
        }
        return count;
    }

    public static int numberOfNiceSubarrays(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    public static void main(String[] args) {
        int[] nums = {1,1,2,1,1};
        int k = 3;
        int result = numberOfNiceSubarrays(nums, k);
        System.out.println("Number of nice subarrays: " + result); // 2
    }
}

function atMost(nums, k) {
  let left = 0, count = 0, oddCount = 0;
  for (let right = 0; right < nums.length; right++) {
    if (nums[right] % 2 !== 0) oddCount++;
    while (oddCount > k) {
      if (nums[left] % 2 !== 0) oddCount--;
      left++;
    }
    count += right - left + 1;
  }
  return count;
}

function numberOfNiceSubarrays(nums, k) {
  return atMost(nums, k) - atMost(nums, k - 1);
}

// Example usage
const nums = [1,1,2,1,1];
const k = 3;
const result = numberOfNiceSubarrays(nums, k);
console.log(`Number of nice subarrays: ${result}`); // 2

package main

import "fmt"

func atMost(nums []int, k int) int {
    left, count, oddCount := 0, 0, 0
    for right := 0; right < len(nums); right++ {
        if nums[right]%2 != 0 {
            oddCount++
        }
        for oddCount > k {
            if nums[left]%2 != 0 {
                oddCount--
            }
            left++
        }
        count += right - left + 1
    }
    return count
}

func numberOfNiceSubarrays(nums []int, k int) int {
    return atMost(nums, k) - atMost(nums, k-1)
}

func main() {
    nums := []int{1, 1, 2, 1, 1}
    k := 3
    result := numberOfNiceSubarrays(nums, k)
    fmt.Printf("Number of nice subarrays: %d\n", result) // 2
}

fn at_most(nums: &[i32], k: i32) -> i32 {
    let mut left = 0;
    let mut count = 0;
    let mut odd_count = 0;
    for right in 0..nums.len() {
        if nums[right] % 2 != 0 {
            odd_count += 1;
        }
        while odd_count > k {
            if nums[left] % 2 != 0 {
                odd_count -= 1;
            }
            left += 1;
        }
        count += (right - left + 1) as i32;
    }
    count
}

fn number_of_nice_subarrays(nums: &[i32], k: i32) -> i32 {
    at_most(nums, k) - at_most(nums, k - 1)
}

fn main() {
    let nums = vec![1, 1, 2, 1, 1];
    let k = 3;
    let result = number_of_nice_subarrays(&nums, k);
    println!("Number of nice subarrays: {}", result); // 2
}

fun atMost(nums: IntArray, k: Int): Int {
    var left = 0
    var count = 0
    var oddCount = 0
    for (right in nums.indices) {
        if (nums[right] % 2 != 0) oddCount++
        while (oddCount > k) {
            if (nums[left] % 2 != 0) oddCount--
            left++
        }
        count += right - left + 1
    }
    return count
}

fun numberOfNiceSubarrays(nums: IntArray, k: Int): Int {
    return atMost(nums, k) - atMost(nums, k - 1)
}

fun main() {
    val nums = intArrayOf(1,1,2,1,1)
    val k = 3
    val result = numberOfNiceSubarrays(nums, k)
    println("Number of nice subarrays: $result") // 2
}

func atMost(_ nums: [Int], _ k: Int) -> Int {
    var left = 0, count = 0, oddCount = 0
    for right in 0 ..< nums.count {
        if nums[right] % 2 != 0 {
            oddCount += 1
        }
        while oddCount > k {
            if nums[left] % 2 != 0 {
                oddCount -= 1
            }
            left += 1
        }
        count += right - left + 1
    }
    return count
}

func numberOfNiceSubarrays(_ nums: [Int], _ k: Int) -> Int {
    return atMost(nums, k) - atMost(nums, k - 1)
}

let nums = [1,1,2,1,1]
let k = 3
let result = numberOfNiceSubarrays(nums, k)
print("Number of nice subarrays: \(result)") // 2

function atMost(nums: number[], k: number): number {
  let left = 0, count = 0, oddCount = 0;
  for (let right = 0; right < nums.length; right++) {
    if (nums[right] % 2 !== 0) oddCount++;
    while (oddCount > k) {
      if (nums[left] % 2 !== 0) oddCount--;
      left++;
    }
    count += right - left + 1;
  }
  return count;
}

function numberOfNiceSubarrays(nums: number[], k: number): number {
  return atMost(nums, k) - atMost(nums, k - 1);
}

// Example usage
const nums = [1,1,2,1,1];
const k = 3;
const result = numberOfNiceSubarrays(nums, k);
console.log(`Number of nice subarrays: ${result}`); // 2

Time complexity

Space complexity

O(1)

The algorithm uses a constant amount of extra space for variables like left, right, oddCount, and result counters. No additional data structures are used, making the space complexity constant.