##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2488.html

# 2488. Count Subarrays With Median K

• Difficulty: Hard.
• Related Topics: Array, Hash Table, Prefix Sum.
• Similar Questions: Number of Subarrays with Bounded Maximum, Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold.

## Problem

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:

The median of an array is the **middle **element after sorting the array in **ascending **order. If the array is of even length, the median is the **left **middle element.

• For example, the median of [2,3,1,4] is 2, and the median of [8,4,3,5,1] is 4.

• A subarray is a contiguous part of an array.

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.

## Solution (Java, C++, Python)

• class Solution {
public int countSubarrays(int[] nums, int k) {
int n = nums.length;
int i = 0;
for (int j = 0; j < n; ++j) {
if (nums[j] == k) {
i = j;
break;
}
}
int ans = 1;
int[] d = new int[n << 1 | 1];
int mi = 0, mx = 0;
for (int j = i + 1; j < n; ++j) {
if (nums[j] < k) {
++mi;
} else {
++mx;
}
if (mx - mi >= 0 && mx - mi <= 1) {
++ans;
}
++d[mx - mi + n];
}
mi = 0;
mx = 0;
for (int j = i - 1; j >= 0; --j) {
if (nums[j] < k) {
++mi;
} else {
++mx;
}
if (mx - mi >= 0 && mx - mi <= 1) {
++ans;
}
ans += d[mi - mx + n] + d[mi - mx + 1 + n];
}
return ans;
}
}

• class Solution {
public:
int countSubarrays(vector<int>& nums, int k) {
int n = nums.size();
int i = 0;
for (int j = 0; j < n; ++j) {
if (nums[j] == k) {
i = j;
break;
}
}
int ans = 1;
int d[n << 1 | 1];
memset(d, 0, sizeof d);
int mi = 0, mx = 0;
for (int j = i + 1; j < n; ++j) {
if (nums[j] < k) ++mi;
else ++mx;
if (mx - mi >= 0 && mx - mi <= 1) ++ans;
++d[mx - mi + n];
}
mi = 0, mx = 0;
for (int j = i - 1; ~j; --j) {
if (nums[j] < k) ++mi;
else ++mx;
if (mx - mi >= 0 && mx - mi <= 1) ++ans;
ans += d[mi - mx + n] + d[mi - mx + n + 1];
}
return ans;
}
};

• class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
i = next(i for i, v in enumerate(nums) if v == k)
n = len(nums)
ans = 1
d = defaultdict(int)
mi = mx = 0
for j in range(i + 1, n):
if nums[j] < k:
mi += 1
else:
mx += 1
if 0 <= mx - mi <= 1:
ans += 1
d[mx - mi] += 1
mi = mx = 0
for j in range(i - 1, -1, -1):
if nums[j] < k:
mi += 1
else:
mx += 1
if 0 <= mx - mi <= 1:
ans += 1
ans += d[mi - mx] + d[mi - mx + 1]
return ans


• func countSubarrays(nums []int, k int) int {
i, n := 0, len(nums)
for nums[i] != k {
i++
}
ans := 1
cnt := make([]int, n<<1|1)
x := 0
for j := i + 1; j < n; j++ {
if nums[j] > k {
x++
} else {
x--
}
if x >= 0 && x <= 1 {
ans++
}
cnt[x+n]++
}
x = 0
for j := i - 1; j >= 0; j-- {
if nums[j] > k {
x++
} else {
x--
}
if x >= 0 && x <= 1 {
ans++
}
ans += cnt[-x+n] + cnt[-x+1+n]
}
return ans
}

• function countSubarrays(nums: number[], k: number): number {
const i = nums.indexOf(k);
const n = nums.length;
const cnt = new Array((n << 1) | 1).fill(0);
let ans = 1;
let x = 0;
for (let j = i + 1; j < n; ++j) {
x += nums[j] > k ? 1 : -1;
ans += x >= 0 && x <= 1 ? 1 : 0;
++cnt[x + n];
}
x = 0;
for (let j = i - 1; ~j; --j) {
x += nums[j] > k ? 1 : -1;
ans += x >= 0 && x <= 1 ? 1 : 0;
ans += cnt[-x + n] + cnt[-x + 1 + n];
}
return ans;
}



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).