Watch 10 video solutions for Count Subarrays With Median K, a hard level problem involving Array, Hash Table, Prefix Sum. This walkthrough by Programming Pathshala has 3,724 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: Given an integer array nums and a value k, count the number of subarrays where the median is exactly k. A valid subarray must contain k, and the number of elements greater than k and less than k must satisfy the balance required for k to be the median.
Approach 1: Two Pointers with Median Validation (O(n²) time, O(1) space)
This direct approach enumerates every subarray that contains k. First locate the index of k, then expand subarrays using two pointers while checking whether the median remains k. For each candidate subarray, count elements greater than and less than k, and verify the balance condition that defines a valid median. The implementation relies only on simple iteration over the array, so space usage stays constant. However, repeatedly validating subarrays leads to quadratic time complexity, which becomes slow for large inputs. This method is useful for understanding the median condition and works as a baseline before applying more advanced techniques.
Approach 2: Prefix Sum with Count Balance (O(n) time, O(n) space)
The optimal solution converts the median condition into a balance problem. Treat each element relative to k: assign +1 if a number is greater than k, -1 if smaller, and 0 for k. A subarray has median k when the balance between larger and smaller values is either 0 or 1. Start from the index of k and compute running balances to the right. Store frequency counts of balances in a hash table. Then traverse to the left and look up complementary balances that satisfy the median condition.
This technique leverages a prefix sum-style transformation. Instead of evaluating each subarray independently, you track cumulative differences and reuse previously computed counts. Every lookup is O(1), so the full scan runs in linear time. The key insight is that median constraints can be reduced to a simple equality between prefix balances. This removes the need for repeated subarray checks and scales efficiently even when the array size approaches the upper constraint limits.
Recommended for interviews: Interviewers typically expect the prefix-sum balance solution. The brute-force or two-pointer expansion demonstrates that you understand how median constraints translate into counts of elements greater or smaller than k. The hash-map prefix technique shows stronger algorithmic thinking by converting the problem into a balance lookup and achieving O(n) time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers with Median Validation | O(n²) | O(1) | Conceptual baseline when learning how median constraints work in subarrays |
| Prefix Sum with Count Balance | O(n) | O(n) | Best general solution for large arrays and typical interview expectations |