Count Subarrays With Median K solution and explanation
Google
9 more videos on this problem
2488 Count subarrays with median K l leetcode Weekly Contest 321Programming Pathshala · 16:25 · 3K views
Weekly Contest 321 | Count Subarrays With Median KcodingMohan · 23:57 · 3K views
Leetcode Weekly contest 321 - Hard - Count Subarrays With Median KPrakhar Agrawal · 10:57 · 3K views
【每日一题】LeetCode 2488. Count Subarrays With Median KHuifeng Guan · 21:23 · 1K views
2488. Count Subarrays With Median K (Leetcode Hard)Programming Live with Larry · 44:12 · 1K views
Count Subarrays With Median K - HashMap - PythonCheatCode Ninja · 10:27 · 1K views
Leetcode Weekly contest 321 - Hard - Count Subarrays With Median K|Complete solution +explanationCode With Singh · 19:02 · 938 views
Count Subarrays With Median K (Leetcode Weekly 321)Soumya Bhattacharjee · 14:48 · 777 views
Leetcode | 2488. Count Subarrays With Median K | C++CyCode · 10:38 · 356 views
#leetcode Weekly Contest 321 || Remove Nodes From Linked List || Count Subarrays With Median KLitCode · 21:36 · 117 views
The 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]is2, and the median of[8,4,3,5,1]is4.
- For example, the median of
- 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.length1 <= n <= 1051 <= nums[i], k <= n- The integers in
numsare distinct.
Approach overview
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 1: Prefix Sum with Count Balance
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.
def count_subarrays_with_median(nums, k):
k_index = nums.index(k)
balance = 0
count = {0: 1}
result = 0
for i in range(k_index, len(nums)):
balance += (nums[i] > k) - (nums[i] < k)
result += count.get(balance, 0) + count.get(balance - 1, 0)
balance = 0
count = {0: 1}
for i in range(k_index - 1, -1, -1):
balance += (nums[i] > k) - (nums[i] < k)
count[balance] = count.get(balance, 0) + 1
return resultimport java.util.HashMap;
public int countSubarraysWithMedian(int[] nums, int k) {
int kIndex = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == k) {
kIndex = i;
break;
}
}
int balance = 0, result = 0;
HashMap<Integer, Integer> count = new HashMap<>();
count.put(0, 1);
for (int i = kIndex; i < nums.length; i++) {
balance += (nums[i] > k ? 1 : nums[i] < k ? -1 : 0);
result += count.getOrDefault(balance, 0) + count.getOrDefault(balance - 1, 0);
}
balance = 0;
count.clear();
count.put(0, 1);
for (int i = kIndex - 1; i >= 0; i--) {
balance += (nums[i] > k ? 1 : nums[i] < k ? -1 : 0);
count.put(balance, count.getOrDefault(balance, 0) + 1);
}
return result;
}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.
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.
Approach 2: Two Pointers with Median Validation
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.
#include <stdio.h>
#include <stdbool.h>
bool isValidMedian(int *nums, int start, int end, int k) {
int length = end - start + 1;
int *temp = malloc((length) * sizeof(int));
int index = 0;
for (int i = start; i <= end; i++) {
temp[index++] = nums[i];
}
qsort(temp, length, sizeof(int), compare);
int median = temp[(length - 1) / 2];
free(temp);
return median == k;
}
int countSubarraysWithMedian(int *nums, int numsSize, int k) {
int count = 0;
for (int start = 0; start < numsSize; start++) {
for (int end = start; end < numsSize; end++) {
if (isValidMedian(nums, start, end, k)) {
count++;
}
}
}
return count;
}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 3: Traversal + Counting
First, we find the position i of the median k in the array, and then start traversing from i to both sides, counting the number of subarrays with a median of k.
Define an answer variable ans, which represents the number of subarrays with a median of k. Initially, ans = 1, which means that there is currently a subarray of length 1 with a median of k. In addition, define a counter cnt, used to count the number of differences between the "number of elements larger than k" and the "number of elements smaller than k" in the currently traversed array.
Next, start traversing to the right from i + 1. We maintain a variable x, which represents the difference between the "number of elements larger than k" and the "number of elements smaller than k" in the current right subarray. If x \in [0, 1], then the median of the current right subarray is k, and the answer variable ans is incremented by 1. Then, we add the value of x to the counter cnt.
Similarly, start traversing to the left from i - 1, also maintaining a variable x, which represents the difference between the "number of elements larger than k" and the "number of elements smaller than k" in the current left subarray. If x \in [0, 1], then the median of the current left subarray is k, and the answer variable ans is incremented by 1. If -x or -x + 1 is also in the counter, it means that there is currently a subarray that spans both sides of i, with a median of k, and the answer variable ans increases the corresponding value in the counter, that is, ans += cnt[-x] + cnt[-x + 1].
Finally, return the answer variable ans.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array.
In coding, we can directly open an array of length
2 times n + 1, used to count the difference between the "number of elements larger thank" and the "number of elements smaller thank" in the current array. Each time we add the difference byn, we can convert the range of the difference from[-n, n]to[0, 2n].
class Solution {
public:
int countSubarrays(vector<int>& nums, int k) {
int n = nums.size();
int i = find(nums.begin(), nums.end(), k) - nums.begin();
int cnt[n << 1 | 1];
memset(cnt, 0, sizeof(cnt));
int ans = 1;
int x = 0;
for (int j = i + 1; j < n; ++j) {
x += nums[j] > k ? 1 : -1;
if (x >= 0 && x <= 1) {
++ans;
}
++cnt[x + n];
}
x = 0;
for (int j = i - 1; ~j; --j) {
x += nums[j] > k ? 1 : -1;
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum with Count Balance | Time Complexity: Space Complexity: |
| Two Pointers with Median Validation | Time Complexity: Space Complexity: |
| Traversal + Counting | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Count Subarrays With Median K easy or hard?
Count Subarrays With Median K is classified as a Hard problem because the key insight is not obvious. The challenge lies in converting the median requirement into a prefix balance condition and counting matches efficiently using a hash map.
Count Subarrays With Median K Python/Java solution
Python and Java implementations typically use a dictionary or HashMap to store prefix balance counts. The algorithm scans from the index of k, updates balance values, and accumulates matches that satisfy the median condition. Both implementations achieve O(n) time complexity.
How to solve Count Subarrays With Median K in O(n)?
Transform the array relative to k by mapping numbers greater than k to +1 and numbers smaller than k to -1. Starting from the index of k, maintain prefix balances and store their frequencies in a hash table. While scanning the opposite direction, look up complementary balances that form 0 or 1 difference, which indicates a valid median configuration.
What is the best approach for Count Subarrays With Median K?
The prefix sum with count balance approach is the most efficient solution. It converts each element into +1 or -1 depending on whether it is greater or smaller than k, then tracks cumulative balances using a hash map. Matching balances determine valid subarrays where k becomes the median. This method runs in O(n) time with O(n) extra space.
Is Count Subarrays With Median K asked at Google/Amazon/Meta?
Median and prefix-balance style problems frequently appear in interviews at companies like Google, Amazon, and Meta. This problem specifically tests understanding of prefix sums, hash maps, and transforming constraints into balance equations. It is commonly used as a hard-level interview practice problem.
What data structure is used in Count Subarrays With Median K?
The optimal solution relies on a hash table (hash map) to store frequencies of prefix balance values. Combined with a prefix sum transformation, the hash map allows constant-time lookups to count valid subarrays efficiently.
What is the time complexity of Count Subarrays With Median K?
The optimal algorithm runs in O(n) time using a prefix sum balance and hash map. Each element is processed once while performing constant-time lookups. A simpler enumeration approach that validates every candidate subarray takes O(n²) time.