Median-Anchored Stretches
HardArrays & Hashing
Problem
Contestants are lined up, and nums[i] is the rank of the person at position i: nums is a permutation of 1..n. A judge picks a contiguous group and announces its median rank. The median of a group is its middle value after sorting; for an even-sized group it is the lower of the two middle values.
Given nums and a rank k, return the number of non-empty contiguous subarrays whose median is exactly k.
Example 1
- Input:
- nums = [2, 5, 1, 4, 3], k = 3
- Output:
- 5
[3], [4, 3], [1, 4, 3], [2, 5, 1, 4, 3] and [5, 1, 4, 3] (sorted [1, 3, 4, 5], lower middle 3).
Example 2
- Input:
- nums = [3, 1, 2], k = 2
- Output:
- 2
[2] and [3, 1, 2].
Constraints
- 1 ≤ n ≤ 10^5
- nums is a permutation of 1..n
- 1 ≤ k ≤ n
Hint
Show the first hint
Any stretch with median k must contain k itself. Only how many elements are bigger or smaller than k matters, not their exact values.
Walkthrough
How to approach it
01Clarify before coding
- Which middle for even sizes? The lower one.
- Is nums a permutation? Yes, so k appears exactly once and all values are distinct.
- Are subarrays counted by position? Yes.
02Brute force
For each subarray, sort it (or keep an ordered structure while extending) and check the median.
Cost: O(n² log n) time with incremental structures (O(n³ log n) sorting each): far too slow for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.