Count Subarrays With Median K - Leetcode Solution

Problem Statement: Given an array of integers nums and an integer k, return the number of contiguous subarrays where the median equals k. The median of a subarray is the middle element when the elements are sorted in non-decreasing order. If the subarray has an odd length, the middle element is the median. If there is an even number of elements in the subarray, the median is the average of the two middle elements.

Example 1: Input: nums = [1,1,3], k = 2 Output: 0 Explanation: The median of the 2 subarrays [1,1] and [1,3] is 1, which is not equal to k.

Example 2: Input: nums = [1,2,3,4,5], k = 3 Output: 3 Explanation: There are 3 subarrays with a median equal to 3: [1,2,3], [2,3,4], and [3,4,5].

Approach: To solve the given problem statement, we can start by iterating over all contiguous subarrays of sizes n, where n is the length of the given array nums. We can then calculate the median of each of the subarrays and compare it with k. If the median is equal to k, we can increment the count.

To calculate the median of the subarray, we can sort the subarray in non-decreasing order and calculate the median accordingly. If the length of the subarray is odd, the median will be the middle element. If the length of the subarray is even, the median will be the average of the two middle elements.

Algorithm:

1. Initialize a count variable to 0.
2. Iterate over all subarrays of size n, where n is the length of the given array nums.
3. Sort the current subarray in non-decreasing order.
4. Calculate the median of the subarray using the above-mentioned approach.
5. If the median of the subarray is equal to k, increment the count.
6. Return the count.

Code:

class Solution { public: int countSubArraysWithMedianK(vector<int>& nums, int k) { int n = nums.size(), count = 0; for(int i = 0; i < n; i++) { for(int j = i; j < n; j++) { vector<int> sub(nums.begin()+i, nums.begin()+j+1); sort(sub.begin(), sub.end()); int median = 0; if(sub.size() % 2 == 0) median = (sub[sub.size()/2-1] + sub[sub.size()/2])/2; else median = sub[sub.size()/2]; if(median == k) count++; } } return count; } };

Time Complexity: O(n^3 log n), as we are iterating over all subarrays of size n and sorting each subarray, which takes O(n log n) time.

Space Complexity: O(n) as we are storing each subarray in the vector of size n.

1