Count Subarrays With Median K — Problem & Solution
Count Subarrays With Median K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Count Subarrays With Median K is a hard coding problem on arrays, hash table and prefix sum, asked in Amazon, Google and Sprinklr interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Prefix Sum
- Asked at: Amazon, Google, Sprinklr
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of length n holding the distinct integers 1 to n (a permutation), and an integer k that occurs in nums.
Return the number of non-empty contiguous subarrays whose median equals k.
The median of an array is its middle element after sorting it in ascending order. When the length is even, the median is the left of the two middle elements — the median of [2,3,1,4] is 2, and the median of [8,4,3,5,1] is 4.
Example 1
Input: nums = [2,5,1,4,3], k = 4
Output: 2
Explanation: `[4]` and `[5,1,4]` (sorted `[1,4,5]`).
Example 2
Input: nums = [4,6,2,5,1,3], k = 4
Output: 5
Explanation: `[4]`, `[4,6]`, `[4,6,2]`, `[4,6,2,5]` and `[4,6,2,5,1]`. Adding the 3 tips the balance to the smaller side.
Example 3
Input: nums = [1,2], k = 1
Output: 2
Explanation: `[1]`, and `[1,2]` whose left-middle element is 1.
Constraints
n == nums.length1 <= n <= 10^51 <= nums[i], k <= nThe integers innumsare distinct.
Hints for Count Subarrays With Median K
Hint 1
A subarray can only have median
kif it containskitself.Hint 2
Only how each element compares to
kmatters. In a window containingk, letgbe the number of elements greater thankandsthe number smaller. When iskthe (left) middle element?Hint 3
kis the median exactly wheng - sis 0 or 1. Writeg - sas (balance of the part left ofk) + (balance of the part right ofk): count the left balances in a table, then for each right extension look up how many left balances complete it to 0 or 1.
How to solve Count Subarrays With Median K
Replace each element by +1 if it is greater than k, -1 if smaller. A window that contains k has median k exactly when the sum of these signs (its balance) is 0 or 1, and that balance splits into an independent left part and right part around k's position.
Approach
- Find
pos, the index ofk. - Walk left from
pos(including the empty extension): keep a running balance ofnums[pos-1], nums[pos-2], …and count how many left extensions produce each balance value. - Walk right from
pos(again starting with the empty extension) with its own running balanceb. - For each right extension, the windows that work pair it with a left extension of balance
-bor1 - b; add both counts. - Return the total.
Why it works
With distinct values, after sorting a window of length m that contains k, k sits at index s (the number of smaller elements). The left median sits at index floor((m - 1) / 2) with m = s + g + 1, and s = floor((s + g) / 2) holds exactly when g = s or g = s + 1. The window's balance g - s is the left part's balance plus the right part's balance, and every (left extension, right extension) pair is a distinct window, so the counting covers each window exactly once.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Include the empty extension on both sides —
[k]alone, and windows wherekis at an end. - Balances run from
-nton; offset them bynto use an array, or use a hash map. - Even length uses the left middle, which is why balance 1 (one more greater element) is accepted but balance -1 is not.
Reference solution
Python
from typing import List
def countSubarrays(nums: List[int], k: int) -> int:
n = len(nums)
pos = nums.index(k)
cnt = [0] * (2 * n + 2)
bal = 0
cnt[n] = 1
for i in range(pos - 1, -1, -1):
bal += 1 if nums[i] > k else -1
cnt[bal + n] += 1
ans = 0
bal = 0
for j in range(pos, n):
if j > pos:
bal += 1 if nums[j] > k else -1
ans += cnt[n - bal] + cnt[n + 1 - bal]
return ansJava
public static int countSubarrays(int[] nums, int k) {
int n = nums.length, pos = 0;
for (int i = 0; i < n; i++) if (nums[i] == k) pos = i;
int[] cnt = new int[2 * n + 2];
int bal = 0;
cnt[n] = 1;
for (int i = pos - 1; i >= 0; i--) {
bal += nums[i] > k ? 1 : -1;
cnt[bal + n]++;
}
long ans = 0;
bal = 0;
for (int j = pos; j < n; j++) {
if (j > pos) bal += nums[j] > k ? 1 : -1;
ans += cnt[n - bal] + cnt[n + 1 - bal];
}
return (int) ans;
}C++
int countSubarrays(vector<int>& nums, int k) {
int n = nums.size(), pos = 0;
for (int i = 0; i < n; i++) if (nums[i] == k) pos = i;
vector<int> cnt(2 * n + 2, 0);
int bal = 0;
cnt[n] = 1;
for (int i = pos - 1; i >= 0; i--) {
bal += nums[i] > k ? 1 : -1;
cnt[bal + n]++;
}
long long ans = 0;
bal = 0;
for (int j = pos; j < n; j++) {
if (j > pos) bal += nums[j] > k ? 1 : -1;
ans += cnt[n - bal] + cnt[n + 1 - bal];
}
return (int) ans;
}JavaScript
var countSubarrays = function(nums, k) {
var n = nums.length, pos = 0;
for (var i = 0; i < n; i++) if (nums[i] === k) pos = i;
var cnt = new Array(2 * n + 2).fill(0);
var bal = 0;
cnt[n] = 1;
for (var i = pos - 1; i >= 0; i--) {
bal += nums[i] > k ? 1 : -1;
cnt[bal + n]++;
}
var ans = 0;
bal = 0;
for (var j = pos; j < n; j++) {
if (j > pos) bal += nums[j] > k ? 1 : -1;
ans += cnt[n - bal] + cnt[n + 1 - bal];
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets