Even Odd Count

The Problem

Given an integer array arr and an integer k, count the number of contiguous subarrays of size exactly k that contain an equal number of even and odd integers.

A window of size k can only have an equal even/odd split when k is even (half even, half odd). If k is odd, an equal split is impossible — return 0 immediately.

arr = [2, 3, 4, 5, 6],  k = 4  →  2
arr = [1, 2, 3, 4],     k = 2  →  3
arr = [1, 1, 1],        k = 2  →  0
arr = [2, 4, 6, 8],     k = 2  →  0
arr = [1, 2, 3, 4, 5],  k = 3  →  0   (k is odd — impossible)

Examples

Example 1

Input:  arr = [2, 3, 4, 5, 6],  k = 4
Output: 2
Explanation:
  Window [2,3,4,5]: 2 even (2,4), 2 odd (3,5)  ✓
  Window [3,4,5,6]: 2 even (4,6), 2 odd (3,5)  ✓

Example 2

Input:  arr = [1, 2, 3, 4],  k = 2
Output: 3
Explanation:
  Window [1,2]: 1 even, 1 odd  ✓
  Window [2,3]: 1 even, 1 odd  ✓
  Window [3,4]: 1 even, 1 odd  ✓

Example 3

Input:  arr = [1, 1, 1],  k = 2
Output: 0
Explanation: Every window has 0 even and 2 odd — no equal split.

Intuition

Track the count of even numbers in the current window. A window has an equal split when exactly k // 2 elements are even (and therefore k // 2 are odd).

The add/remove logic:

• Element entering is even → even_count += 1
• Element leaving is even → even_count -= 1
• Odd elements entering or leaving → no change

At each full-size window, check if even_count == k // 2. If yes, increment the result counter.

One important pre-check: if k is odd, return 0 immediately. You can’t split an odd number into equal halves — it’s mathematically impossible regardless of the array contents.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  PreCheck{"k % 2 != 0?"}
  RetZero(["return 0"])
  Init(["start=0, end=0, even_count=0, result=0"])
  Loop{"end < len(arr)?"}
  Expand["① even_count += 1 if arr[end] is even"]
  Contract{"end − start + 1 > k?"}
  Remove["even_count -= 1 if arr[start] is even<br/>start += 1"]
  Process{"end − start + 1 == k?"}
  Check{"even_count == k // 2?"}
  Inc["result += 1"]
  Advance["end += 1"]
  Done(["return result"])

  PreCheck -->|"yes — equal split impossible"| RetZero
  PreCheck -->|"no"| Init --> Loop
  Loop -->|"yes"| Expand --> Contract
  Contract -->|"yes"| Remove --> Process
  Contract -->|"no"| Process
  Process -->|"yes"| Check
  Process -->|"no"| Advance
  Check -->|"yes"| Inc --> Advance
  Check -->|"no"| Advance
  Advance --> Loop
  Loop -->|"no"| Done

Even Odd Count — pre-check k for odd/even feasibility, then track even count per window. A window qualifies when even_count equals exactly k // 2.

Solution

from typing import List

class Solution:
    def count_equal_even_odd_windows(self, arr: List[int], k: int) -> int:
        # If k is odd, an equal even/odd split is mathematically impossible
        if k % 2 != 0:
            return 0

        # Initialize the window boundaries
        start      = 0
        end        = 0
        # Running count of even numbers in the current window
        even_count = 0
        result     = 0

        while end < len(arr):
            # ① Expand: if the incoming element is even, increment the even count
            if arr[end] % 2 == 0:
                even_count += 1

            # ② Contract: if window grew past k, evict the outgoing element
            if end - start + 1 > k:
                # Remove the outgoing element's contribution to the even count
                if arr[start] % 2 == 0:
                    even_count -= 1
                start += 1

            # ③ Process: when window is exactly k, check for equal even/odd split
            if end - start + 1 == k:
                # Equal split requires exactly k//2 even numbers (and k//2 odd numbers)
                if even_count == k // 2:
                    result += 1

            end += 1

        return result


sol = Solution()
print(sol.count_equal_even_odd_windows([2, 3, 4, 5, 6], 4))   # 2
print(sol.count_equal_even_odd_windows([1, 2, 3, 4], 2))       # 3
print(sol.count_equal_even_odd_windows([1, 1, 1], 2))          # 0
print(sol.count_equal_even_odd_windows([2, 4, 6, 8], 2))       # 0
print(sol.count_equal_even_odd_windows([1, 2, 3, 4, 5], 3))   # 0  (k is odd)
print(sol.count_equal_even_odd_windows([1, 2], 2))             # 1

Dry Run — Example 1

arr = [2, 3, 4, 5, 6], k = 4

k=4 is even → proceed.
start=0, end=0, even_count=0, result=0

end=0: ① arr[0]=2, even → even=1. size=1, not k.
end=1: ① arr[1]=3, odd  → even=1. size=2, not k.
end=2: ① arr[2]=4, even → even=2. size=3, not k.
end=3: ① arr[3]=5, odd  → even=2. ③ size=4==k.
       even=2 == k//2=2 → result=1.   Window [2,3,4,5]: 2 even (2,4), 2 odd (3,5) ✓
end=4: ① arr[4]=6, even → even=3. ② size=5>k → arr[0]=2, even → even=2, start=1.
       ③ size=4==k. even=2 == k//2=2 → result=2.  Window [3,4,5,6]: 2 even (4,6), 2 odd (3,5) ✓
end=5: end >= n=5 → loop exits.

Return: 2 ✓

Why k Odd Returns 0

If k is odd, you’d need k // 2 even numbers and k // 2 odd numbers. But k // 2 + k // 2 = k - 1 (integer division floors), leaving one element unaccounted for. You can’t partition k elements into two equal halves when k is odd — the check even_count == k // 2 would pass only if there are (k-1)/2 evens and (k+1)/2 odds (or vice versa), which is not a balanced split. Catching this early saves unnecessary work.

Complexity Analysis

Edge Cases

Comparison: All Four Fixed Sliding Window Problems

All four use the same template. Only the aggregate definition and the process step differ.

Key Takeaway

Even Odd Count shows the fixed sliding window pattern applied to a parity check. Track even count, slide in O(1), and check the balance condition at each full-size window. The pre-check for odd k is the only problem-specific guard — without it, the even_count == k // 2 condition would never fire for odd k (since k//2 + k//2 < k), silently returning 0 anyway. Adding it explicitly makes the reasoning clear.