982. Median Is K
The array nums holds distinct integers, and k is one of them. A scoreboard reports the median of a block of consecutive entries as follows: sort the block, and take the element in the middle position; if the block has an even length, take the left one of the two middle elements.
Count the non-empty blocks of consecutive entries whose median equals k. Blocks are told apart by their start and end positions. The answer always fits in a 32-bit signed integer for the stated sizes.
Example 1
- Input:
- nums = [4,9,2,7], k = 7
- Output:
- 2
- Explanation:
Only [7] and [9,2,7] have 7 as their (lower) middle value once sorted; [2,7] has middle 2 and the full list has middle 4.
Example 2
- Input:
- nums = [8], k = 8
- Output:
- 1
- Explanation:
The single block [8] has median 8.
Example 3
- Input:
- nums = [10,20,30,40,50], k = 30
- Output:
- 5
- Explanation:
The qualifying blocks are [30], [30,40], [20,30,40], [20,30,40,50] and the whole array, five in total.
Constraints
- 1 ≤ nums.length ≤ 5 * 104
- -109 ≤ nums[i] ≤ 109, all values distinct
- k is an element of nums
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)