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:
[2,3,1,4] is 2, and the median of [8,4,3,5,1] is 4.
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.length1 <= n <= 1051 <= nums[i], k <= nnums are distinct.This approach uses a prefix sum-like method to count subarrays effectively without resorting to checking each subarray individually. Instead of focusing directly on the subarrays, we keep track of the number of elements greater and less than k as we iterate, and use a hashmap to maintain balances, which help find the required subarrays efficiently.
This Python function first finds the index of k and initializes a balance counter. As it iterates over the elements after k, it updates the balance according to whether elements are greater than or less than k. The hashmap stores counts of balances, and the result is updated each time a previous balance (or its decrement by one) can be reused. This effectively counts subarrays with the median k without constructing them explicitly.
Java
Time Complexity: O(n), as we iterate through the array a constant number of times, and hashmap operations are average O(1).
Space Complexity: O(n), for storing the balance counts in a hashmap.
This approach uses a two-pointer technique that expands and contracts a window over the array. At each step, it checks if the current window has k as its median using a running sum structure. This direct approach is simpler but can be less optimal than prefix-based methods.
This C implementation uses a nested loop to examine each subarray and checks if k is the median by sorting. This is done by extracting each relevant subarray and using a simple sort-and-compare process. Although this is a direct implementation, it's less efficient due to repeated sorting.
Time Complexity: O(n^3 log n) due to sorting within the nested loops.
Space Complexity: O(n) for temporary storage of subarrays in each check.
| Approach | Complexity |
|---|---|
| Prefix Sum with Count Balance | Time Complexity: Space Complexity: |
| Two Pointers with Median Validation | Time Complexity: Space Complexity: |
Median of Two Sorted Arrays - Binary Search - Leetcode 4 • NeetCode • 551,948 views views
Watch 9 more video solutions →Practice Count Subarrays With Median K with our built-in code editor and test cases.
Practice on FleetCode