Count subarrays with median k

Array Hash Table Prefix Sum

47.7% acceptance

Feb 25, 2026

654

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. The median of an array is the middle element after sorting (left middle for even length).

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_subarrays(nums: Vec<i32>, k: i32) -> i32 {
    // Find position of k, then use balance scoring
    let pos = nums.iter().position(|&x| x == k).unwrap();
    // For subarray including pos: balance = (#greater) - (#less)
    // Median is k iff balance==0 (odd length) or balance==1 (even length)
    let mut count = 0i32;
    let mut map = std::collections::HashMap::new();
    map.insert(0i32, 1);
    let mut balance = 0i32;
    for i in (0..pos).rev() {
      balance += if nums[i] < k { -1 } else { 1 };
      *map.entry(balance).or_insert(0) += 1;
    }
    balance = 0;
    for j in pos..nums.len() {
      if j != pos {
        balance += if nums[j] < k { -1 } else { 1 };
      }
      count += map.get(&(-balance)).unwrap_or(&0);
      count += map.get(&(-balance + 1)).unwrap_or(&0);
    }
    count
  }
}