Count Subarrays Where Median Equals K [Hard] — Prefix Balance

Problem Statement

Count subarrays of odd length where the median equals k. (Median = middle element after sorting.)

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

Intuition

Map each element: +1 if > k, -1 if < k, 0 if = k. The median = k means the subarray contains k AND the prefix sum of this mapped array is 0 (equal elements or +1 with k present).

For each right, count lefts where prefix balance is 0 (odd length) or -1 (even length, but we need odd length subarrays → balance 0 or 1 after including k's position).

Solutions

Python

from collections import defaultdict

def countSubarrays(nums: list[int], k: int) -> int:
    n = len(nums)
    # find k's index
    ki = nums.index(k)
    # map: > k → +1, < k → -1, == k → 0
    prefix = defaultdict(int)
    prefix[0] = 1
    bal = 0
    ans = 0
    for i in range(ki-1, -1, -1):
        bal += (1 if nums[i] > k else -1)
        prefix[bal] += 1
    bal = 0
    for i in range(ki+1, n):
        bal += (1 if nums[i] > k else -1)
        # subarray contains ki: balance = 0 or 1 means median is k
        ans += prefix[bal] + prefix[bal-1]
    return ans + 1  # single element [k] itself

Complexity

Time: O(n), Space: O(n)