1010HardArrayHash TablePrefix Sum

Stretches Whose Middle Reading Is the Given One

Tracked in this browser only

Trains the technique from

LeetCode 2488Count Subarrays With Median K

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_subarrays(readings: list[int], k: int) -> int:

Java

public int countSubarrays(int[] readings, int k)

The intended approach

Time O(n) over the log's length.Space O(n) for the tally table.

Only whether an entry sits above or below `k` matters, never by how much. Score every entry `1` when it is above `k` and `-1` when below, with `k` itself scoring nothing. A stretch has `k` as its middle reading exactly when it holds `k` and its score adds to `0` or `1`. Ordering an odd stretch puts `k` in the centre when the entries above it match the entries below in number, which is a score of nothing. Ordering an even stretch puts `k` just before the centre when there is exactly one more above than below, a score of one. The lengths look after themselves: a score of nothing forces an odd length and a score of one forces an even one. So find where `k` sits and work outwards from it. Sweep rightwards from that place, keeping the score of the stretch running from `k` to here and tallying how often each score turns up, counting the stretch that stops at `k` itself with a score of nothing. Then sweep leftwards, and for each left score take from the tally the two right scores that finish the sum at `0` or at `1`. Every stretch spanning `k` splits into exactly one left part and one right part, so each is counted once. Two passes and one tally table.

Pythonentry point: count_subarrays

def count_subarrays(readings, k):
    n = len(readings)
    at = 0
    for i in range(n):
        if readings[i] == k:
            at = i
            break
    tally = {0: 1}
    score = 0
    for i in range(at + 1, n):
        score += 1 if readings[i] > k else -1
        tally[score] = tally.get(score, 0) + 1
    total = 0
    score = 0
    for i in range(at, -1, -1):
        if i != at:
            score += 1 if readings[i] > k else -1
        total += tally.get(-score, 0) + tally.get(1 - score, 0)
    return total

The obvious version

Take every stretch of the log, put a copy of it in increasing order, read off the entry at the centre, taking the earlier of two when the length is even, and count the stretch when that entry is `k`. Costs every stretch times the work of ordering it rather than two sweeps and a tally.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_subarrays(readings, k):
    n = len(readings)
    total = 0
    for i in range(n):
        for j in range(i, n):
            part = sorted(readings[i:j + 1])
            if part[(len(part) - 1) // 2] == k:
                total += 1
    return total

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in