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 innums _that have amedian 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.

Examples

Example 1

1
2
3

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

1
2
3

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 <= 10^5
  • 1 <= nums[i], k <= n
  • The integers in nums are distinct.

Solution

Method 1 – Prefix Sum and Hash Map

Intuition

The key is to count subarrays where the number of elements greater than k equals the number of elements less than k, with k as the median. We can map the array to +1 (greater than k), -1 (less than k), and 0 (equal to k), and use prefix sums and a hash map to count valid subarrays.

Approach

  1. Find the index of k in nums (since all elements are distinct).
  2. For each prefix ending at or before the index of k, compute the prefix sum, and count the frequency of each sum in a hash map.
  3. For each prefix starting at the index of k, compute the prefix sum, and for each sum, add the count of that sum and (sum-1) from the hash map to the answer.
  4. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int countSubarrays(int[] nums, int k) {
        int n = nums.length, idx = 0;
        for (int i = 0; i < n; i++) if (nums[i] == k) idx = i;
        Map<Integer, Integer> cnt = new HashMap<>();
        int sum = 0;
        cnt.put(0, 1);
        for (int i = idx-1; i >= 0; i--) {
            sum += nums[i] < k ? -1 : 1;
            cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
        }
        int ans = 0; sum = 0;
        for (int i = idx; i < n; i++) {
            if (i == idx) sum = 0;
            else sum += nums[i] < k ? -1 : 1;
            ans += cnt.getOrDefault(-sum, 0) + cnt.getOrDefault(-sum+1, 0);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def countSubarrays(self, nums: list[int], k: int) -> int:
        n = len(nums)
        idx = nums.index(k)
        from collections import Counter
        cnt = Counter()
        s = 0
        cnt[0] = 1
        for i in range(idx-1, -1, -1):
            s += 1 if nums[i] > k else -1
            cnt[s] += 1
        ans = 0
        s = 0
        for i in range(idx, n):
            if i == idx:
                s = 0
            else:
                s += 1 if nums[i] > k else -1
            ans += cnt[-s] + cnt[-s+1]
        return ans

Complexity

  • ⏰ Time complexity: O(n), since we scan the array twice and use hash maps for prefix sums.
  • 🧺 Space complexity: O(n), for the hash map storing prefix sum counts.