Count Subarrays With Median K

Count Subarrays With Median K

What is this problem about?

The "Count Subarrays With Median K interview question" is a unique array problem that combines the concept of medians with subarray counting. You are given a permutation of integers from 1 to $n$ and a target integer k. You need to find the number of non-empty subarrays where the median is equal to k. The median of a subarray of length $L$ is the element at index $(L - 1) / 2$ in the sorted version of the subarray.

Why is this asked in interviews?

Companies like Salesforce and Amazon ask the "Count Subarrays With Median K coding problem" to test a candidate's ability to transform a value-based property (median) into a frequency-based property (relative counts). It requires the insight that for k to be the median, the number of elements greater than k must be balanced by the number of elements smaller than k. It evaluations knowledge of "Prefix Sum interview pattern" and "Hash Table" optimization.

Algorithmic pattern used

This problem follows the Value Transformation and Hash Map Prefix Sum patterns.

1. Normalization: Replace each element in the array:
   • Elements $> k$ become +1.
   • Elements $< k$ become -1.
   • Element $k$ becomes 0.
2. Median Condition:
   • For odd-length subarrays, the sum of transformed values must be 0 (meaning equal number of $+1$ and $-1$ around $k$).
   • For even-length subarrays, the sum must be 1 (meaning one extra $+1$ so that after sorting, $k$ falls in the median position).
3. Implementation:
   • Locate the index of k.
   • Calculate prefix sums for the left side of k and store their frequencies in a map.
   • Calculate prefix sums for the right side of k.
   • For each right-side prefix sum $S$, the number of valid subarrays is count(S) + count(S-1).

Example explanation

Array: [3, 2, 1, 4, 5], $k = 4$

• Transformed: [-1, -1, -1, 0, 1] (relative to 4).
• Index of 4 is 3.
• Left prefix sums: {0: 1, -1: 1, -2: 1, -3: 1}.
• Right prefix sum at index 4 is 1.
• Target sums from left: $1$ (for even length) and $0$ (for odd length).
• Valid pairs: $(1, 0)$ and $(1, 1)$.
• Result: Sum of matching left prefix counts.

Common mistakes candidates make

• Sorting: Trying to sort every possible subarray to find the median ($O(N^3 \log N)$).
• Ignoring Even/Odd: Only checking for the sum 0 and forgetting the sum 1 case for even-length medians.
• Permutation Property: Forgetting that the array contains unique elements from $1 \dots n$, which simplifies the median definition.

Interview preparation tip

Whenever a problem involves a "Median" and counting subarrays, try to replace values with +1, -1, and 0. This is a classic "Array interview pattern" trick that reduces a complex comparison into a simple prefix sum problem.