Scale Engineer

Count Number of Nice Subarrays

Med
#1165Time: O(N^2), where N is the length of the array. The two nested loops lead to a quadratic time complexity, as we potentially check every subarray.Space: O(1), as we only use a constant number of variables to store counts and indices.2 companies
Patterns
MathSliding WindowPrefix Sum
Data structures
ArrayHash Table
Companies
RobloxDeliveroo

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most straightforward and intuitive approach. The idea is to generate every possible continuous subarray of the given array nums. For each subarray, we count the number of odd integers it contains. If this count is exactly equal to k, we increment a counter for nice subarrays. We repeat this process for all subarrays and return the final count.

Algorithm

  • Initialize a variable nice_count to 0.
  • Use a nested loop structure. The outer loop with index i iterates from 0 to n-1 to fix the starting point of a subarray.
  • The inner loop with index j iterates from i to n-1 to fix the ending point of the subarray.
  • For each subarray nums[i...j], maintain a count of odd numbers within it, let's call it odd_count.
  • As the inner loop extends the subarray by one element nums[j], update odd_count.
  • If odd_count becomes equal to k, it means the current subarray nums[i...j] is nice, so we increment nice_count.
  • If odd_count exceeds k, we can break the inner loop because any further extension of the subarray from this starting point i will also have more than k odd numbers.
  • After iterating through all possible start and end points, return the final nice_count.

Walkthrough

We can implement this using two nested loops. The outer loop selects the starting index i of the subarray, and the inner loop selects the ending index j. For each pair of (i, j), we have a subarray nums[i...j]. A running count of odd numbers is maintained for the subarray as the inner loop progresses. When the count of odd numbers reaches k, we've found a nice subarray and increment our result. A small optimization can be made: if the count of odd numbers exceeds k, we can stop extending the current subarray (break the inner loop) since it can no longer become a nice subarray with exactly k odd numbers.

class Solution {    public int numberOfSubarrays(int[] nums, int k) {        int count = 0;        int n = nums.length;        for (int i = 0; i < n; i++) {            int oddCount = 0;            for (int j = i; j < n; j++) {                if (nums[j] % 2 != 0) {                    oddCount++;                }                if (oddCount == k) {                    count++;                } else if (oddCount > k) {                    // Optimization: No need to check further for this starting 'i'                    break;                }            }        }        return count;    }}

Complexity

Time

O(N^2), where N is the length of the array. The two nested loops lead to a quadratic time complexity, as we potentially check every subarray.

Space

O(1), as we only use a constant number of variables to store counts and indices.

Trade-offs

Pros

  • Simple to understand and easy to implement.

  • Requires no extra space besides a few counter variables.

Cons

  • Highly inefficient for large inputs.

  • Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms given the problem constraints (N up to 50000).

Solutions

class Solution {public  int numberOfSubarrays(int[] nums, int k) {    int n = nums.length;    int[] cnt = new int[n + 1];    cnt[0] = 1;    int ans = 0, t = 0;    for (int v : nums) {      t += v & 1;      if (t - k >= 0) {        ans += cnt[t - k];      }      cnt[t]++;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem