DDSA Solutions

1248. Count Number of Nice Subarrays

MediumView on LeetCode
ArrayHash TableMathSliding WindowPrefix Sum
Time: O(n)
Space: O(1)

Problem Overview

Count subarrays with exactly k odd numbers.

Intuition

Count subarrays with exactly k odd numbers. Use "exactly k" = "at most k" - "at most k-1" with sliding window.

Algorithm

  1. 1atMost(k): sliding window counting subarrays with at most k odd numbers.
  2. 2Answer = atMost(k) - atMost(k-1).

Common Pitfalls

  • •Direct sliding window for "exactly k" is tricky. Difference of at-most functions is cleaner.
1248.cs
C#
// Approach: Sliding window with at-most trick; NumberOfSubarraysAtMost(k) - NumberOfSubarraysAtMost(k-1).
// Time: O(n) Space: O(1)

public class Solution
{
    public int NumberOfSubarrays(int[] nums, int k)
    {
        return NumberOfSubarraysAtMost(nums, k) - NumberOfSubarraysAtMost(nums, k - 1);
    }

    private int NumberOfSubarraysAtMost(int[] nums, int k)
    {
        int ans = 0;

        for (int l = 0, r = 0; r <= nums.Length;)
            if (k >= 0)
            {
                ans += r - l;
                if (r == nums.Length)
                    break;
                if (nums[r] % 2 == 1)
                    --k;
                ++r;
            }
            else
            {
                if (nums[l] % 2 == 1)
                    ++k;
                ++l;
            }

        return ans;
    }
}
Was this solution helpful?

Related Problems