You are given an array nums of size n consisting of distinct integers from 1 to n and a positive integer k.
Return the number of non-empty subarrays in nums that have a median equal to k.
Note:
Examples
Example 1
Input: nums = [3,2,1,4,5], k = 4
Output: 3
Explanation: The subarrays that have a median equal to 4 are: [4], [4,5] and [1,4,5].
Example 2
Input: nums = [2,3,1], k = 3
Output: 1
Explanation: [3] is the only subarray that has a median equal to 3.
Constraints
n == nums.length
1 <= n <= 105
1 <= nums[i], k <= n
The integers in nums are distinct.
2488. Count Subarrays With Median K
Hard
50 Points
Array
Hash Table
Prefix Sum
You are given an array nums of size n consisting of distinct integers from 1 to n and a positive integer k.
Return the number of non-empty subarrays in nums that have a median equal to k.
Note:
Examples
Example 1
Input: nums = [3,2,1,4,5], k = 4
Output: 3
Explanation: The subarrays that have a median equal to 4 are: [4], [4,5] and [1,4,5].
Example 2
Input: nums = [2,3,1], k = 3
Output: 1
Explanation: [3] is the only subarray that has a median equal to 3.
Constraints
n == nums.length
1 <= n <= 105
1 <= nums[i], k <= n
The integers in nums are distinct.
Count Subarrays With Median K - Practice Coding | SlaveCode