Show problems as
Classic problem #2488HardArrayHash TablePrefix Sum

Count Subarrays With Median K

Real-world version: Stretches Whose Middle Reading Is the Given One
Tracked in this browser only
Read Count Subarrays With Median K on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A log holds the readings readings, which are the whole numbers from 1 up to the log's length, each appearing exactly once. A number k in that same range is also given.

The middle reading of a stretch of neighbouring entries is found by putting the stretch in increasing order and taking the entry in the centre. Where the stretch holds an even number of entries, take the earlier of the two central ones.

Return how many stretches have k as their middle reading.

Examples

Example 1

Input
readings = [4, 1, 5, 3, 2], k = 2
Output
3

The reading 2 sits at the far end. On its own it is the middle. With the 3 before it the ordered pair is 2, 3 and the earlier central entry is 2. With 1, 5 and 3 before it the ordered four are 1, 2, 3, 5 and the earlier central entry is again 2. The other two stretches put 3 in the middle instead.

Example 2

Input
readings = [1, 2, 3, 4, 5], k = 3
Output
5

Five stretches work: 3 on its own; 3 with 4; 2, 3 and 4; 2, 3, 4 and 5; and the whole log. In each of them the entries above 3 either match those below in number or run one ahead.

Example 3

Input
readings = [2, 1], k = 2
Output
1

Only the single entry 2 has 2 in the middle. The pair orders to 1, 2 and its earlier central entry is 1.

Constraints

  • 1 <= readings.length <= 10^5
  • The readings are the whole numbers from 1 to readings.length, each appearing once.
  • 1 <= k <= readings.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_subarrays(readings: list[int], k: int) -> int:
Java
public int countSubarrays(int[] readings, int k)

More on the same topics