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.

Description Hints 3 Solution Video 16:25

2488. Count Subarrays With Median K

Hard49.7% acceptance3 companies

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] is 2, and the median of [8,4,3,5,1] is 4.
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.length
1 <= n <= 10⁵
1 <= nums[i], k <= n
The integers in nums are distinct.

Asked at 3 companies

Salesforce Amazon

Google

Topics

Hints open one at a time

Hint 1

Consider changing the numbers that are strictly greater than k in the array to 1, the numbers that are strictly smaller than k to -1, and k to 0.

Hint 2

After the change, what property does a subarray with median k have in the new array?

Hint 3

An array with median k should have a sum equal to either 0 or 1 in the new array and should contain the element k. How do you count such subarrays?

16:25

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution