Count Subarrays With Median K

Hard
1353.

Count Subarrays With Median K

Count Subarrays With Median K is a hard coding problem on arrays, hash table and prefix sum, asked in Amazon, Google and Sprinklr interviews.

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.length
  • 1 <= n <= 10^5
  • 1 <= nums[i], k <= n
  • The integers in nums are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countSubarrays = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • 1 <= n <= 10^5
  • 1 <= nums[i], k <= n
  • The integers in nums are distinct.

Hints for Count Subarrays With Median K

  1. Hint 1

    A subarray can only have median k if it contains k itself.

  2. Hint 2

    Only how each element compares to k matters. In a window containing k, let g be the number of elements greater than k and s the number smaller. When is k the (left) middle element?

  3. Hint 3

    k is the median exactly when g - s is 0 or 1. Write g - s as (balance of the part left of k) + (balance of the part right of k): 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

  1. Find pos, the index of k.
  2. Walk left from pos (including the empty extension): keep a running balance of nums[pos-1], nums[pos-2], … and count how many left extensions produce each balance value.
  3. Walk right from pos (again starting with the empty extension) with its own running balance b.
  4. For each right extension, the windows that work pair it with a left extension of balance -b or 1 - b; add both counts.
  5. 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 where k is at an end.
  • Balances run from -n to n; offset them by n to 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 ans

Java

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